oj.uz

Submission #886690

# Submission time Handle Problem Language Result Execution time Memory
886690 2023-12-12T16:24:26 Z AgentPengin Watching (JOI13_watching) C++14
100 / 100
 332 ms 31860 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2005;

int n,P,Q,a[MAXN];
pair<int,int> dp[MAXN][MAXN];

inline void maximize(pair<int,int>& u,const pair<int,int> v) {
	if (v.fi < u.fi) u = v;
	else if (v.fi == u.fi && v.se > u.se) u = v;
}

bool check(int mid) {
	// dp[i] = {P,Q} -> uu tien su dung P truoc Q sau
	// dp[i][j] -> the first i-th, use j type 1, fi type 2, go second
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= P;j++) dp[i][j] = make_pair(inf,0);
	}
	dp[1][0] = make_pair(1,2 * mid - 1);
	dp[1][1] = make_pair(0,mid - 1);
	
	for (int i = 1;i < n;i++) {
		for (int j = 0;j <= P;j++) {
			if (a[i + 1] - a[i] <= dp[i][j].se) {
				maximize(dp[i + 1][j],make_pair(dp[i][j].fi,dp[i][j].se - (a[i + 1] - a[i])));
			}
			if (j < P)
			maximize(dp[i + 1][j + 1],make_pair(dp[i][j].fi,mid - 1));
			
			maximize(dp[i + 1][j],make_pair(dp[i][j].fi + 1,2 * mid - 1));
		}
	}
	
	for (int j = 0;j <= P;j++) {
		if (dp[n][j].fi <= Q) return true;
	}
	return false;	
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> P >> Q;
    if (P + Q >= n) return cout << 1,0;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1,a + n + 1);
	int l = 1,r = 1e9,ans = 1e9;
	while(l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
    
    cout << ans;
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid = l + r >> 1;
      |             ~~^~~
watching.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2520 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2576 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31324 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 31332 KB Output is correct
8 Correct 32 ms 31324 KB Output is correct
9 Correct 143 ms 31640 KB Output is correct
10 Correct 332 ms 31860 KB Output is correct
11 Correct 20 ms 31320 KB Output is correct
12 Correct 194 ms 31708 KB Output is correct
13 Correct 6 ms 31320 KB Output is correct
14 Correct 8 ms 31324 KB Output is correct
15 Correct 8 ms 31304 KB Output is correct