Submission #1285489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285489		shine	Stove (JOI18_stove)	C++20	100 / 100	19 ms	2248 KiB

stove

//--------------------------------- 
#include <bits/stdc++.h>
using namespace std;

//---------------------------------
#ifdef DEBUG
#define debug(x) {cout<<"---> "<<#x<<" = "<<x<<endl;}
#else
#define debug(x)
#endif 
//--------------------------------- 
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ff first
#define ss second
#define endl "\n"
#define pii pair<int,int>
#define REP(a, c) for (int(a) = 0; (a) < (c); (a)++)
#define FOR(a, b, c) for (int(a) = (b); (a) <= (c); (a)++)
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
#define tpl tuple<int,int,int> 
#define ld long double 
#define subtract(x) ((~(x)) ^ (1 << __builtin_ctz(x) + 1) - 1)
//---------------------------------
#define _task "text"
inline void _FILE() {
    if(fopen(_task ".inp", "r")) {
        freopen(_task ".inp", "r", stdin);
        freopen(_task ".out", "w", stdout);
    }
}
//---------------------------------
const int maxK = 1e3 + 5;
const int maxL = 1e4 + 5;
const int maxM = 1e5 + 5;
const int maxN = 1e6 + 5;
const int maxP = 1e7 + 5;
const long long inf = 1e18;
const int mod = 1e9 + 7;
//---------------------------------
int n, k, dp[2005][2005], a[maxN], pre[maxN], mi[maxN];

void subtask1()
{
    for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j] = inf;
    dp[0][0] = 0;
    for(int j = 1; j <= k; j++){
        for(int i = 1; i <= n; i++){
            for(int t = i; t >= 1; t--){
                dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] - a[t] + a[i] + 1);
            }
        }
    }
    cout << dp[n][k] << endl;
}
void subtask2()
{
    for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j] = inf;
    dp[0][0] = 0;
    for(int j = 1; j <= k; j++){
        mi[0] = inf;
        for(int i = 1; i <= n; i++){
            mi[i] = min(mi[i - 1], dp[i - 1][j - 1] - a[i]);
        }
        for(int i = 1; i <= n; i++){
            dp[i][j] = mi[i] + a[i] + 1;
        }
    } 
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= k; j++){
    //         if(dp[i][j] >= inf) dp[i][j] = -1;
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    cout << dp[n][k] << endl;
}
void subtask3(){
    priority_queue<int> pq;
    int sum = a[n] + 1 - a[1];
    for(int i = 1; i < n; i++){
        pq.push(a[i + 1] - a[i] - 1);
    }
    for(int i = 1; i < k; i++){
        int u = pq.top();
        pq.pop();
        sum -= u; 
    }
    cout << sum;
}
signed main()
{   
    faster
    _FILE();    
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    if(n <= 200) subtask1();
    else if(n <= 2000) subtask2();
    else subtask3();  
    #ifndef ONLINE_JUDEGE
        cerr << "Time elapsed: " << clock() * 1.0 / CLOCKS_PER_SEC << "s.\n";
    #endif
    return 0;
}

Compilation message (stderr)

stove.cpp: In function 'void _FILE()':
stove.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(_task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(_task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50