| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1066772 | 2024-08-20T06:53:23 Z | hasan2006 | Radio Towers (IOI22_towers) | C++17 | 4000 ms | 7376 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e5 + 9 , mod = 1e9 + 7;
int b[N] , dp[N] , c[N] , d[N] , n , t[N] ;
vector<int>a;
void count_dp(int l , int r , int k){
int mx = 0 , i , j , x , y , s , f , m;
d[r] = 1;
f = r;
set<int>st;
int mn = a[r];
for(i = r - 1; i >= l; i--){
if(a[i] > mx){
d[i] = d[f];
if(a[i] - k >= mn)
mx = max(mx , a[i] - k);
mn = min(mn , a[i]);
}else{
d[i] = d[f] + 1;
mn= a[i];
mx = 0;
f = i;
}
d[i] = max(d[i] , d[i + 1]);
}
}
void init(int n , vector<int>a){
::a = a;
::n = n;
count_dp(0 , n - 1 , 1);
}
int max_towers(int l ,int r , int k){
if(k == 1)
return d[r] - d[l] + 1;
int mx = 0 , i , j , x , y , s , f , m;
dp[r] = 1;
f = r;
set<int>st;
int mn = a[r];
for(i = r - 1; i >= l; i--){
if(a[i] > mx){
dp[i] = dp[f];
if(a[i] - k >= mn)
mx = max(mx , a[i] - k);
mn = min(mn , a[i]);
}else{
dp[i] = dp[f] + 1;
mn= a[i];
mx = 0;
f = i;
}
dp[i] = max(dp[i] , dp[i + 1]);
}
return dp[l];
}
/*
int main(){
TL;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
/*
init(7, {10, 20, 60, 40, 50, 30, 70});
cout<<max_towers(0 , 6, 17)<<"\n";
}*/
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2836 ms | 4972 KB | Output is correct |
| 2 | Execution timed out | 4002 ms | 7376 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 1 ms | 4440 KB | Output is correct |
| 3 | Correct | 1 ms | 4440 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 KB | Output is correct |
| 5 | Correct | 1 ms | 4440 KB | Output is correct |
| 6 | Correct | 1 ms | 4440 KB | Output is correct |
| 7 | Correct | 1 ms | 4440 KB | Output is correct |
| 8 | Correct | 1 ms | 4440 KB | Output is correct |
| 9 | Correct | 1 ms | 4440 KB | Output is correct |
| 10 | Correct | 1 ms | 4440 KB | Output is correct |
| 11 | Correct | 1 ms | 4440 KB | Output is correct |
| 12 | Incorrect | 0 ms | 2392 KB | 1st lines differ - on the 1st token, expected: '2', found: '0' |
| 13 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 1 ms | 4440 KB | Output is correct |
| 3 | Correct | 1 ms | 4440 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 KB | Output is correct |
| 5 | Correct | 1 ms | 4440 KB | Output is correct |
| 6 | Correct | 1 ms | 4440 KB | Output is correct |
| 7 | Correct | 1 ms | 4440 KB | Output is correct |
| 8 | Correct | 1 ms | 4440 KB | Output is correct |
| 9 | Correct | 1 ms | 4440 KB | Output is correct |
| 10 | Correct | 1 ms | 4440 KB | Output is correct |
| 11 | Correct | 1 ms | 4440 KB | Output is correct |
| 12 | Incorrect | 0 ms | 2392 KB | 1st lines differ - on the 1st token, expected: '2', found: '0' |
| 13 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 422 ms | 5464 KB | 1st lines differ - on the 1st token, expected: '11903', found: '-11901' |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3513 ms | 4804 KB | Output is correct |
| 2 | Execution timed out | 4051 ms | 7376 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 1 ms | 4440 KB | Output is correct |
| 3 | Correct | 1 ms | 4440 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 KB | Output is correct |
| 5 | Correct | 1 ms | 4440 KB | Output is correct |
| 6 | Correct | 1 ms | 4440 KB | Output is correct |
| 7 | Correct | 1 ms | 4440 KB | Output is correct |
| 8 | Correct | 1 ms | 4440 KB | Output is correct |
| 9 | Correct | 1 ms | 4440 KB | Output is correct |
| 10 | Correct | 1 ms | 4440 KB | Output is correct |
| 11 | Correct | 1 ms | 4440 KB | Output is correct |
| 12 | Incorrect | 0 ms | 2392 KB | 1st lines differ - on the 1st token, expected: '2', found: '0' |
| 13 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2836 ms | 4972 KB | Output is correct |
| 2 | Execution timed out | 4002 ms | 7376 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |