oj.uz

Submission #1093064

# Submission time Handle Problem Language Result Execution time Memory
1093064 2024-09-25T19:07:11 Z Seb Potatoes and fertilizers (LMIO19_bulves) C++17
20 / 100
 1000 ms 1460 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T> //order_of_key = menores, find_by_order = consultar indexado en 0, regresa iterador
using ordered_set =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vii = vector<int>;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define mid ((l+r)>>1)
#define f first
#define s second
#define pb push_back
#define MP make_pair
#define all(x) (x).begin(),(x).end()
#define inicio(x) (*(x).begin())
#define rinicio(x) (*(x).rbegin())
#define SZ(x) (int)(x.size())

const ll MAXN = (ll)3e3 + 5;
const ll MAXK = (ll)3e4 + 5;
const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e12 + 5;
const ll OFFSET = (ll)1e6;

ll dp[2][MAXK], sum;

void tc() {
    ll N; cin >> N;
    for (int i = 0; i < N; i++) {
        ll a, b; cin >> a >> b;
        a -= b;
        sum += a;

        for (int j = 0; j < MAXK; j++) {
            if (i) {
                dp[i&1][j] = dp[(i - 1)&1][j];
                if (j) dp[i&1][j] = min(dp[i&1][j], dp[i&1][j - 1]);
            }
        }
        for (int j = 0; j < MAXK; j++) dp[i&1][j] += abs(j - sum);
    }

    cout << dp[(N - 1)&1][sum] << "\n";
    return;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        tc();
    }
    return 0;
}

//checa tus constantes, n = 1? overflow?

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 304 ms 856 KB Output is correct
3 Correct 305 ms 856 KB Output is correct
4 Execution timed out 1068 ms 924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 304 ms 856 KB Output is correct
3 Correct 305 ms 856 KB Output is correct
4 Execution timed out 1068 ms 924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 304 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 101 ms 912 KB Output is correct
5 Correct 156 ms 856 KB Output is correct
6 Correct 314 ms 920 KB Output is correct
7 Correct 318 ms 924 KB Output is correct
8 Correct 305 ms 860 KB Output is correct
9 Correct 308 ms 856 KB Output is correct
10 Correct 307 ms 856 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 304 ms 856 KB Output is correct
3 Correct 305 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 101 ms 912 KB Output is correct
6 Correct 156 ms 856 KB Output is correct
7 Correct 314 ms 920 KB Output is correct
8 Correct 318 ms 924 KB Output is correct
9 Correct 305 ms 860 KB Output is correct
10 Correct 308 ms 856 KB Output is correct
11 Correct 307 ms 856 KB Output is correct
12 Runtime error 207 ms 1460 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 304 ms 856 KB Output is correct
3 Correct 305 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 101 ms 912 KB Output is correct
6 Correct 156 ms 856 KB Output is correct
7 Correct 314 ms 920 KB Output is correct
8 Correct 318 ms 924 KB Output is correct
9 Correct 305 ms 860 KB Output is correct
10 Correct 308 ms 856 KB Output is correct
11 Execution timed out 1068 ms 924 KB Time limit exceeded
12 Halted 0 ms 0 KB -