oj.uz

Submission #386136

# Submission time Handle Problem Language Result Execution time Memory
386136 2021-04-05T17:19:36 Z tko919 Aliens (IOI16_aliens) C++17
0 / 100
 5 ms 4332 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
   using P=pair<int,int>;
   vector<P> pos,used;
   rep(i,0,n){
      if(r[i]>c[i])swap(r[i],c[i]);
      pos.push_back({r[i],c[i]});
   }
   sort(ALL(pos),[](P& a,P& b){
      if(a.first==b.first)return a.second>b.second;
      else return a.first<b.first;
   });
   int mx=-1;
   rep(i,0,n){
      if(!chmax(mx,pos[i].second))continue;
      used.push_back(pos[i]);
   }

   n=used.size();
   int nxt=1;
   ll from[510][510],to[510][510];
   rep(i,0,n+5)rep(j,0,k+5)from[i][j]=INF;
   from[0][0]=0;
   for(auto& p:used){
      rep(i,0,n+5)rep(j,0,k+5)to[i][j]=INF;
      rep(i,0,n+5)rep(j,0,k+1)if(from[i][j]!=INF){
         if(p!=used.back()){
            chmin(to[i][j],from[i][j]);
         }
         ll add=1LL*(p.second-used[i].first+1)*(p.second-used[i].first+1);
         if(i)add-=max(0LL,1LL*(used[i].first-used[i-1].second+1)*(used[i].first-used[i-1].second+1));
         chmin(to[nxt][j+1],from[i][j]+add);
      }
      swap(from,to);
      nxt++;
   }

   ll res=INF;
   rep(j,1,k+1)chmin(res,from[n][j]);
   return res;
}

/*
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);
    
    
    printf("%lld\n", ans);
    return 0;
}
//*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 4
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 4
4 Correct 5 ms 4332 KB Correct answer: answer = 12
5 Incorrect 5 ms 4332 KB Wrong answer: output = 64, expected = 52
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 1
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 1
4 Incorrect 5 ms 4332 KB Wrong answer: output = 1, expected = 5
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 4
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 4
4 Correct 5 ms 4332 KB Correct answer: answer = 12
5 Incorrect 5 ms 4332 KB Wrong answer: output = 64, expected = 52
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 4
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 4
4 Correct 5 ms 4332 KB Correct answer: answer = 12
5 Incorrect 5 ms 4332 KB Wrong answer: output = 64, expected = 52
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 4
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 4
4 Correct 5 ms 4332 KB Correct answer: answer = 12
5 Incorrect 5 ms 4332 KB Wrong answer: output = 64, expected = 52
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4332 KB Correct answer: answer = 4
2 Correct 4 ms 4332 KB Correct answer: answer = 4
3 Correct 4 ms 4332 KB Correct answer: answer = 4
4 Correct 5 ms 4332 KB Correct answer: answer = 12
5 Incorrect 5 ms 4332 KB Wrong answer: output = 64, expected = 52
6 Halted 0 ms 0 KB -