Submission #1251495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251495		raysh07	Radio Towers (IOI22_towers)	C++17	27 / 100	4046 ms	1564 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9

int n;
vector <int> a;
 
void init(int N, vector<int> H) {
    n = N;
    a.resize(n);
    for (int i = 0; i < n; i++){
        a[i] = H[i];
    }
}
 
int max_towers(int l, int r, int d) {
    int ans = 1;
    int best = INF;
    int mx = -INF;
    for (int i = l; i <= r; i++){
        if (max(a[i], best) + d <= mx){
            ans++;
            best = a[i];
            mx = -INF;
        } else {
            if (a[i] < best){
                best = a[i];
                mx = -INF;
            } else {
                mx = max(mx, a[i]);
            }
        }
    }
    return ans;
}

// int brute(int l, int r, int d){
//     vector <int> dp(n);
//     int ans = 0;
//     for (int i = l; i <= r; i++){
//         dp[i] = 1;
//         for (int j = l; j < i; j++){
//             bool good = false;
//             for (int k = j; k <= i; k++){
//                 good |= a[k] >= max(a[i], a[j]) + d;
//             }
            
//             if (good){
//                 dp[i] = max(dp[i], dp[j] + 1);
//             }
//         }
//         ans = max(ans, dp[i]);
//     }
    
//     return ans;
// }

// mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

// void solve(){
//     // int n; cin >> n;
//     int n = 1 + RNG() % 3;
    
//     vector <int> A(n);
//     for (int i = 0; i < n; i++){
//         // cin >> A[i];
//         A[i] = 1 + RNG() % 20;
//     }
    
//     init(n, A);
    
//     // int q; cin >> q;
//     int q = 10;
//     while (q--){
//         // int l, r, d; cin >> l >> r >> d;
//         int l = RNG() % n;
//         int r = RNG() % n;
//         if (l > r) swap(l, r);
//         int d = 1 + RNG() % 10;
        
//         if (max_towers(l, r, d) != brute(l, r, d)){
//             cout << "WA\n";
//             cout << n << "\n";
//             for (int i = 0; i < n; i++){
//                 cout << A[i] << " \n"[i + 1 == n];
//             }
//             cout << l << " " << r << " " << d << "\n";
//             cout << max_towers(l, r, d) << " " << brute(l, r, d) << "\n";
//             exit(0);
//         }
//     }
// }

// int main(){
//     int t; cin >> t;
//     while (t--){
//         solve();
//     }
//     return 0;
// }

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23