Submission #1022578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022578		JakobZorz	Radio Towers (IOI22_towers)	C++17	0 / 100	4035 ms	3308 KiB

towers

#include"towers.h"
#include<vector>
#include<iostream>
using namespace std;

vector<int>arr;

void init(int N,vector<int>H){
    arr=H;
}

int solve(vector<int>arr,int d){
    vector<int>arr2=arr;
    arr.clear();
    arr2.insert(arr2.begin(),1e9+1);
    arr2.push_back(1e9+1);
    
    for(int i=1;i<(int)arr2.size()-1;i++){
        if(arr2[i-1]<arr2[i]&&arr2[i+1]<arr2[i])
            arr.push_back(arr2[i]);
        if(arr2[i-1]>arr2[i]&&arr2[i+1]>arr2[i])
            arr.push_back(arr2[i]);
    }
    
    while(true){
        bool removed=false;
        for(int i=1;i<(int)arr.size();i+=2){
            if(arr[i]-max(arr[i-1],arr[i+1])<d){
                removed=true;
                arr[i-1]=min(arr[i-1],arr[i+1]);
                arr.erase(arr.begin()+i);
                arr.erase(arr.begin()+i);
                break;
            }
        }
        if(!removed)
            break;
    }
    
    return (arr.size()+1)/2;
}

int max_towers(int L,int R,int D){
    vector<int>arr2;
    for(int i=L;i<=R;i++)
        arr2.push_back(arr[i]);
    return solve(arr2,D);
}

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