oj.uz

Submission #469456

# Submission time Handle Problem Language Result Execution time Memory
469456 2021-09-01T03:29:41 Z robell Stove (JOI18_stove) C++17
20 / 100
 1000 ms 23756 KB 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
int mod = 1e9+7;
void setIO(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
void setIO(string f){
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
	setIO();
}
int N, K;
int t[100001];
int main(){
	setIO();
	cin >> N >> K;
	for (int i=0;i<N;i++) cin >> t[i];
	ll dp[N][K+1];
	for (int i=0;i<N;i++){
		if (i==0) dp[i][1]=0;
		else dp[i][1]=t[i]-t[i-1]+dp[i-1][1];
	}
	for (int k=2;k<=K;k++){
		for (int i=0;i<N;i++){
			dp[i][k]=1e18;
			for (int j=0;j<i;j++){
				dp[i][k]=min(t[i-1]+1-t[j]+dp[j][k-1],dp[i][k]);
			}
		}
	}
	ll totmin = 1e18;
	for (int i=0;i<N;i++){
		totmin=min(dp[i][K]+t[N-1]+1-t[i],totmin);
	}
	cout << totmin << "\n";
}

Compilation message

stove.cpp: In function 'void setIO(std::string)':
stove.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen((f+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:20:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  freopen((f+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 85 ms 600 KB Output is correct
11 Correct 959 ms 2712 KB Output is correct
12 Execution timed out 1091 ms 23756 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 85 ms 600 KB Output is correct
11 Correct 959 ms 2712 KB Output is correct
12 Execution timed out 1091 ms 23756 KB Time limit exceeded
13 Halted 0 ms 0 KB -