Submission #2742019


Source Code Expand

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); i++)

int dp[100+1][100*5000+1];

inline void chmax(int &a, const int b) {
  a = max(a, b);
}

void solve(const int n) {
  REP(i,n+1) REP(j,n*5000+1) dp[i][j] = -1;
  dp[0][0] = 0;
  vector<int> p(n);
  REP(i,n) cin>>p[i];
  REP(i,n) {
    int rem = 1000-p[i]%1000;
    if(rem==1000) rem = 0;
    for(int j = 0; j <= i*5000; j++) {
      if(dp[i][j] < 0) continue;
      chmax(dp[i+1][j],dp[i][j]);
      chmax(dp[i+1][j+p[i]],dp[i][j]+rem);
    }
  }
  int ans1 = 0;
  int ans2 = 1<<30;
  for(int j = 0; j <= n*5000; j++) {
    if(dp[n][j]/500 > ans1) {
      ans1 = dp[n][j]/500;
      ans2 = j;
    }
  }
  cout << ans1 << " " << ans2 << endl;
}


int main() {
  int n; 
  while(cin>>n, n) {
    solve(n);
  }
  return 0;
}

Submission Info

Submission Time
Task C - Tak and Cards
User kmatsunaga
Language C++14 (GCC 5.4.1)
Score 0
Code Size 937 Byte
Status TLE
Exec Time 2104 ms
Memory 101888 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 100
Status
TLE × 4
TLE × 12
TLE × 24
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt TLE 2103 ms 17024 KB
example_02.txt TLE 2103 ms 17024 KB
example_03.txt TLE 2103 ms 17024 KB
example_04.txt TLE 2103 ms 64896 KB
subtask1_01.txt TLE 2104 ms 97536 KB
subtask1_02.txt TLE 2104 ms 99584 KB
subtask1_03.txt TLE 2104 ms 99584 KB
subtask1_04.txt TLE 2103 ms 33536 KB
subtask1_05.txt TLE 2103 ms 99584 KB
subtask1_06.txt TLE 2104 ms 99584 KB
subtask1_07.txt TLE 2103 ms 58240 KB
subtask1_08.txt TLE 2104 ms 70656 KB
subtask1_09.txt TLE 2104 ms 95488 KB
subtask2_01.txt TLE 2104 ms 99584 KB
subtask2_02.txt TLE 2104 ms 99584 KB
subtask2_03.txt TLE 2104 ms 97536 KB
subtask2_04.txt TLE 2104 ms 99584 KB
subtask2_05.txt TLE 2104 ms 99584 KB
subtask2_06.txt TLE 2104 ms 101888 KB
subtask2_07.txt TLE 2104 ms 99584 KB
subtask2_08.txt TLE 2103 ms 64512 KB
subtask2_09.txt TLE 2103 ms 76928 KB
subtask2_10.txt TLE 2103 ms 81024 KB
subtask2_11.txt TLE 2104 ms 85120 KB