oj.uz

Submission #92790

# Submission time Handle Problem Language Result Execution time Memory
92790 2019-01-04T14:41:16 Z updown1 Kas (COCI17_kas) C++17
100 / 100
 298 ms 196468 KB 
/*
https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/COCI/official/2017/contest4_solutions/solutions.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 1, N+1)
#define ffj For(j, 0, 100001)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=501, INF=1000000000;
///500,000,000
int N, inp[MAXN], dp[MAXN][100001], tot;
/// dp[ind][abs(diff money)] = min left over money

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	ffi {cin >> inp[i]; tot += inp[i];}
	For (i, 0, N+1) ffj dp[i][j] = INF;
	dp[0][0] = 0;
	ffa {
        dp[i][j] = min(dp[i][j], dp[i-1][j]+inp[i]);
        if (j >= inp[i]) dp[i][j] = min(dp[i][j], dp[i-1][j-inp[i]]);
        if (j+inp[i] < 100001) dp[i][j] = min(dp[i][j], dp[i-1][j+inp[i]]);
        if (inp[i] >= j) dp[i][j] = min(dp[i][j], dp[i-1][inp[i]-j]);
	}
	w<< dp[N][0] + (tot-dp[N][0])/2<<e;
}

Compilation message

kas.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 7 ms 4600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 7 ms 4600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4728 KB Output is correct
2 Correct 8 ms 4856 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 9 ms 5752 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14456 KB Output is correct
2 Correct 25 ms 16376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18296 KB Output is correct
2 Correct 30 ms 20352 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 78968 KB Output is correct
2 Correct 140 ms 98652 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 118188 KB Output is correct
2 Correct 232 ms 157368 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 176888 KB Output is correct
2 Correct 298 ms 196468 KB Output is correct