Submission #1290027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290027		MMihalev	Radio Towers (IOI22_towers)	C++20	0 / 100	313 ms	33184 KiB

towers

#include<iostream>
#include<algorithm>
#include "towers.h"
#include <vector>
#include<set>
using namespace std;
int ma[2005][2005];
set<int> used[2005];
int which[2005][2005];
vector<int>h;
void init(int N, std::vector<int> H)
{
    h=H;
    for(int i=0;i<N;i++)
    {
        ma[i][i]=h[i];
        which[i][i]=i;
        for(int j=i+1;j<N;j++)
        {
            if(ma[i][j-1]>h[j])
            {
                which[i][j]=which[i][j-1];
            }
            else which[i][j]=j;

            ma[i][j]=max(ma[i][j-1],h[j]);
        }
    }
}

int max_towers(int L, int R, int D)
{
   bool ima=0;
   for(int i=L;i<=R;i++)
   {
       for(int j=i+2;j<=R;j++)
       {
           if(ma[i+1][j-1]-D>=max(h[i],h[j]))
           {
               used[which[i+1][j-1]].insert(i);
               used[which[i+1][j-1]].insert(j);
               ima=1;
           }
       }
   }
   if(!ima)return 1;
   int cnt=0;
   for(int i=L;i<=R;i++)
   {
       cnt=max(cnt,(int)(used[i].size()));
   }
   return cnt;
}

• 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