Submission #1205935

#TimeUsernameProblemLanguageResultExecution timeMemory
1205935loiiii12358Aliens (IOI16_aliens)C++20
25 / 100
2082 ms840 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define int long long struct cht{ vector<pair<int,int>> lines; vector<int> test; void add(int m, int c){ lines.push_back({m,c}); } int query(int x){ int ans=1e13; for(int i=0;i<lines.size();i++){ ans=min(ans,lines[i].first*x+lines[i].second); } return ans; } }; long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) { vector<int> dp(n+1,1e13),a(n+1,0),b(n+1,0),gc={0},gr={0}; vector<pair<int,int>> points; deque<pair<int,int>> dq; int tmp,ans=1e13; for(int i=0;i<n;i++){ if(r[i]>c[i]){ swap(r[i],c[i]); } points.push_back({c[i],r[i]}); } sort(points.begin(),points.end()); for(int i=0;i<points.size();i++){ while(!dq.empty()&&dq.back().second>=points[i].second){ dq.pop_back(); } dq.push_back(points[i]); } for(int i=0;i<dq.size();i++){ gc.push_back(dq[i].first+1); gr.push_back(dq[i].second+1); } for(int i=0;i<dq.size();i++){ if(gc[i]-gr[i+1]+1>=0){ a[i]=2-2*gr[i+1]; b[i]=(gc[i]+2-2*gr[i+1])*(-gc[i]); }else{ a[i]=2-2*gr[i+1]; b[i]=(1-gr[i+1])*(1-gr[i+1]); } // cout << a[i] << ' ' << b[i] << '\n'; } dp[0]=0; for(int i=1;i<=k;i++){ cht now; now.add(a[0],b[0]); for(int j=1;j<=dq.size();j++){ tmp=gc[j]*gc[j]+now.query(gc[j]); now.add(a[j],b[j]+dp[j]); dp[j]=tmp; // cout << dp[j] << " \n"[j==dq.size()]; } ans=min(ans,tmp); } return ans; }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...