제출 #618114

#제출 시각아이디문제언어결과실행 시간메모리
618114rrrr10000Aliens (IOI16_aliens)C++14
25 / 100
2079 ms6996 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<P> vp; typedef vector<vp> vvp; typedef vector<bool> vb; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++) #define all(a) a.begin(),a.end() #define lb(v,k) (lower_bound(all(v),k)-v.begin()) #define fi first #define se second #define pb emplace_back template<class T> void out(T a){cout<<a<<endl;} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;} template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;} const ll inf=1001001001001001001; long long take_photos(int n, int m, int K, std::vector<int> r, std::vector<int> c) { vp srt(n); rep(i,n)srt[i]=P(max(r[i],c[i]),min(r[i],c[i])); sort(all(srt)); vp v;v.pb(-1,-1); for(auto x:srt){ while(v.size()&&v.back().fi>=x.se)v.pop_back(); if(v.size()==0||v.back().se<x.fi)v.pb(x.se,x.fi); } n=v.size(); vvi dp(n,vi(K+1,inf)); dp[0][0]=0; rep(i,n)rep(j,K)if(dp[i][j]!=inf){ chmin(dp[i][j+1],dp[i][j]); REP(t,i+1,n)chmin(dp[t][j+1],dp[i][j]+(v[t].se-v[i+1].fi+1)*(v[t].se-v[i+1].fi+1)-max(0ll,v[i].se-v[i+1].fi+1)*max(0ll,v[i].se-v[i+1].fi+1)); } return dp[n-1][K]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...