oj.uz

Submission #790131

# Submission time Handle Problem Language Result Execution time Memory
790131 2023-07-22T10:57:25 Z n3rm1n Stove (JOI18_stove) C++17
50 / 100
 1000 ms 3608 KB 
/// note: it's actually stove
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, k, a[MAXN];

void read()
{
    cin >> n >> k;
    for (long long i = 1; i <= n; ++ i)
        cin >> a[i];
}

vector < long long > before(MAXN), dp(MAXN);
long long inf = 1e15+10;
long long q = 0;
void divide(long long l, long long r, long long opt_left, long long opt_right)
{
    if(l > r)return;

    //cout << l << " " << r << endl;
    long long mid = (l + r)/2;
    dp[mid] = inf;
    long long best = inf, best_opt = -1;
    long long cost;
    for (long long cut = opt_left; cut <= min(mid, opt_right); ++ cut)
    {
        cost = before[cut-1] + a[mid] - a[cut] + 1;
       /* if(q == 2)
        {
            cout << "**" << endl;
            cout << l << " " << r << " --> " << mid << endl;
            cout << "cut on " << cut << endl;
            cout << cost << endl;
        }*/
        if(cost < best)
        {
            best = cost;
            best_opt = cut;
        }
    }
    dp[mid] = best;
    //cout << q << " " << mid << " " << best << endl;
    divide(l, mid-1, opt_left, best_opt);
    divide(mid+1, r, best_opt, opt_right);

}
void solve()
{
    dp[0] = 0;
    for (long long i = 1; i <= n; ++ i)
        dp[i] = inf;
    for (long long i = 1; i <= k; ++ i)
    {
        q = i;
        before = dp;
        divide(1, n, 1, n);
    }
    cout << dp[n] << endl;
}
int main()
{
   // speed();

    read();
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1892 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1892 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct
11 Correct 10 ms 1948 KB Output is correct
12 Correct 83 ms 1876 KB Output is correct
13 Correct 142 ms 1876 KB Output is correct
14 Correct 187 ms 1928 KB Output is correct
15 Correct 188 ms 1924 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1892 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct
11 Correct 10 ms 1948 KB Output is correct
12 Correct 83 ms 1876 KB Output is correct
13 Correct 142 ms 1876 KB Output is correct
14 Correct 187 ms 1928 KB Output is correct
15 Correct 188 ms 1924 KB Output is correct
16 Correct 47 ms 3536 KB Output is correct
17 Correct 232 ms 3608 KB Output is correct
18 Execution timed out 1077 ms 3500 KB Time limit exceeded
19 Halted 0 ms 0 KB -