#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
typedef long long llong;
const int MAXN = 3000 + 10;
const int MAXAB = 30000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int abs(int num)
{
if (num < 0) return -num;
return num;
}
llong abs(llong num)
{
if (num < 0) return -num;
return num;
}
int n;
int c[MAXN];
llong dp[MAXN][2*MAXAB];
void solve()
{
for (int i = 0 ; i < 2 * MAXAB ; ++i)
{
dp[n + 1][i] = INF;
}
dp[n + 1][MAXAB] = 0;
for (int pos = n ; pos >= 1 ; --pos)
{
for (int bal = 2 * MAXAB - 1 ; bal >= 0 ; --bal)
{
dp[pos][bal] = INF;
if (bal + 1 < 2 * MAXAB)
{
dp[pos][bal] = dp[pos][bal + 1];
}
if (bal - c[pos] >= 0)
{
dp[pos][bal] = std::min(dp[pos][bal], dp[pos + 1][bal - c[pos]] + abs(bal - c[pos] - MAXAB));
}
}
}
std::cout << dp[1][MAXAB] << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> c[i];
int val; std::cin >> val;
c[i] -= val;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3540 KB |
Output is correct |
2 |
Runtime error |
210 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3540 KB |
Output is correct |
2 |
Runtime error |
210 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3540 KB |
Output is correct |
2 |
Runtime error |
210 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3540 KB |
Output is correct |
2 |
Runtime error |
210 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3540 KB |
Output is correct |
2 |
Runtime error |
210 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |