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 |
|
|
|
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 |