Submission #795304

#	Time	Username	Problem	Language	Result	Execution time	Memory
795304		ln_e	Radio Towers (IOI22_towers)	C++17	0 / 100	36 ms	16152 KiB

towers

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
    #include "towers.h"
    using ll=long long;
    using ld=long double;
    int const INF=1000000005;
    ll const LINF=1000000000000000005;
    ll const mod=1000000007;
    ld const PI=3.14159265359;
    ll const MAX_N=3e5+5;
    ld const EPS=0.00000001;
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define endl '\n'
    #define sz(a) (int)a.size()
    #define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    using namespace std;
int a[2005],dp[2005][2005],n;
map<ll,ll>viz;
void init(int N, std::vector<int> H) {
  vector<ll>compress;
  n=N;
  for(ll i=0;i<N;i++)
  {
    compress.pb(H[i]);
  }
  sort(compress.begin(),compress.end());
  ll val=0;
  for(ll i=0;i<compress.size();i++)
  {
    if(i==0||compress[i]!=compress[i-1]){
      viz[compress[i]]=++val;
    }
  }
for(ll i=0;i<N;i++)
{
  a[i+1]=viz[H[i]];
}
}
int max_towers(int L, int R, int D) {
for(ll i=L+1;i<=R+1;i++)
{
  int val=0;
  val=a[i-1];
  for(ll j=0;j<=n;j++)
  {
    dp[i][j]=dp[i-1][j];
  }
for(ll j=i-2;j>=L+1;j--)
{
  if(a[i]<=val-D){
    dp[i][val-D]=max(dp[i][val-D],1+dp[j][val-D]);
  }
  val=max(val,a[j]);
}
dp[i][a[i]]=max(dp[i][a[i]],1);
for(ll j=1;j<=n;j++)
{
dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
}
int ans=0;
for(ll j=0;j<=n;j++)
  ans=max(ans,dp[R+1][j]);
return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:32:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(ll i=0;i<compress.size();i++)
      |              ~^~~~~~~~~~~~~~~~

• 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