oj.uz

Submission #1085323

# Submission time Handle Problem Language Result Execution time Memory
1085323 2024-09-08T00:40:15 Z trMatherz Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 208 ms 42152 KB 
#include <iostream> //cin, cout


// #include <fstream>
// std::ifstream cin ("tallbarn.in");
// std::ofstream cout ("tallbarn.out");





// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>


//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define ld long double
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()
#define vc vector<char>
#define vvc vector<vc>


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)


int main(){
    int n; cin >> n; 
    vl a, b;
    int suma = 0, sumb = 0;
    F(i, n) {
        int x; cin >> x; a.pb(x); suma += x;
        cin >> x; b.pb(x); sumb += x; 
    }
    vvl dp(n + 1, vl(suma - sumb + 1, 0));
    ll cur = 0;
    F(i, n){
        cur += a[i] - b[i]; 
        F(j, suma - sumb + 1) {
            dp[i + 1][j] = dp[i][j] + abs(abs(cur) - j);
            if(j != 0) emin(dp[i + 1][j], dp[i + 1][j - 1]); 
        }
    }
    // A(u, dp){
    //     A(l, u) cout << l << " ";
    //     cout << endl;
    // }
    cout << dp[n][suma - sumb]; 
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 15 ms 4048 KB Output is correct
5 Correct 36 ms 7864 KB Output is correct
6 Correct 118 ms 21316 KB Output is correct
7 Correct 208 ms 42152 KB Output is correct
8 Correct 173 ms 40420 KB Output is correct
9 Correct 198 ms 39848 KB Output is correct
10 Correct 115 ms 37540 KB Output is correct
11 Correct 127 ms 37536 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 15 ms 4048 KB Output is correct
5 Correct 36 ms 7864 KB Output is correct
6 Correct 118 ms 21316 KB Output is correct
7 Correct 208 ms 42152 KB Output is correct
8 Correct 173 ms 40420 KB Output is correct
9 Correct 198 ms 39848 KB Output is correct
10 Correct 115 ms 37540 KB Output is correct
11 Correct 127 ms 37536 KB Output is correct
12 Incorrect 52 ms 10928 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 12 ms 16200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 12 ms 16200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 12 ms 16200 KB Output isn't correct
6 Halted 0 ms 0 KB -