oj.uz

Submission #604913

# Submission time Handle Problem Language Result Execution time Memory
604913 2022-07-25T10:47:53 Z StrawHatWess Meetings (IOI18_meetings) C++17
19 / 100
 3740 ms 786432 KB 
#include "meetings.h"

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

typedef long long ll; 
typedef vector<int>vi; 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)

typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi; 
#define eb emplace_back

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void ckmax(ll &x, ll y){x=max(x,y);}
void ckmin(ll &x, ll y){x=min(x,y);}
//--------------------

int N,Q; 

vector<ll> minimum_costs(vi H, vi L, vi R) {
	N=sz(H); Q=sz(L); 

	vector<vector<ll>>c(N,vector<ll>(N,0ll));
	FOR(i,0,N){
		FOR(j,i,N){
			c[i][j]=H[j]; 
			if(j>i) ckmax(c[i][j],c[i][j-1]); 
		}

		ROF(j,0,i){
			c[i][j]=H[j]; 
			ckmax(c[i][j],c[i][j+1]); 
		}

		FOR(j,1,N) c[i][j]+=c[i][j-1]; 
	}

	vector<ll>ans; 
	FOR(i,0,Q){
		int l=L[i], r=R[i]; 

		ll mn=1e18; 

		FOR(m,l,r+1){
			ll x=c[m][m]; if(l) x-=c[m][l-1]; 
			ll y=c[m][r]-c[m][m]; 
			ckmin(mn,x+y); 
		}

		ans.pb(mn); 
	}
	return ans; 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 82 ms 70856 KB Output is correct
3 Correct 88 ms 70916 KB Output is correct
4 Correct 81 ms 70888 KB Output is correct
5 Correct 80 ms 70916 KB Output is correct
6 Correct 82 ms 70860 KB Output is correct
7 Correct 81 ms 70908 KB Output is correct
8 Correct 83 ms 70860 KB Output is correct
9 Correct 82 ms 70904 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 82 ms 70856 KB Output is correct
3 Correct 88 ms 70916 KB Output is correct
4 Correct 81 ms 70888 KB Output is correct
5 Correct 80 ms 70916 KB Output is correct
6 Correct 82 ms 70860 KB Output is correct
7 Correct 81 ms 70908 KB Output is correct
8 Correct 83 ms 70860 KB Output is correct
9 Correct 82 ms 70904 KB Output is correct
10 Correct 447 ms 196504 KB Output is correct
11 Correct 673 ms 196556 KB Output is correct
12 Correct 413 ms 196556 KB Output is correct
13 Correct 673 ms 196556 KB Output is correct
14 Correct 413 ms 196452 KB Output is correct
15 Correct 406 ms 196504 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3740 ms 505696 KB Output is correct
3 Runtime error 297 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3740 ms 505696 KB Output is correct
3 Runtime error 297 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 82 ms 70856 KB Output is correct
3 Correct 88 ms 70916 KB Output is correct
4 Correct 81 ms 70888 KB Output is correct
5 Correct 80 ms 70916 KB Output is correct
6 Correct 82 ms 70860 KB Output is correct
7 Correct 81 ms 70908 KB Output is correct
8 Correct 83 ms 70860 KB Output is correct
9 Correct 82 ms 70904 KB Output is correct
10 Correct 447 ms 196504 KB Output is correct
11 Correct 673 ms 196556 KB Output is correct
12 Correct 413 ms 196556 KB Output is correct
13 Correct 673 ms 196556 KB Output is correct
14 Correct 413 ms 196452 KB Output is correct
15 Correct 406 ms 196504 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 3740 ms 505696 KB Output is correct
18 Runtime error 297 ms 786432 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -