제출 #519109

#제출 시각아이디문제언어결과실행 시간메모리
519109AntekbCultivation (JOI17_cultivation)C++14
80 / 100
2063 ms3192 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("trapv") #define st first #define nd second #define pb(x) push_back(x) #define pp(x) pop_back(x) #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); typedef unsigned int uint; //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=305, INF=1e9+5, mod=1e9+7; pair<int, int> r[N][N]; uint len[N][N]; int tim[N][N]; uint X[N]; int Y[N]; uint M[N]; pair<int, int> find(pair<int, int> x){ if(r[x.st][x.nd]==x)return x; return r[x.st][x.nd]=find(r[x.st][x.nd]); } void Union(int a, int b){ pii u=find(mp(a, b)); if(a==0){ len[u.st][u.nd]=2*INF; return; } pii v=find(mp(a-1, b)); assert(u!=v); r[v.st][v.nd]=u; len[u.st][u.nd]+=len[v.st][v.nd]; } int main(){ //BOOST; int n, w, h; cin>>h>>w>>n; //assert(n<=250); vii pts(n); for(pii &i:pts)cin>>i.st>>i.nd, i.st--, i.nd--; map<int, int> cx, cy; for(int i=0; i<pts.size(); i++){ cx[pts[i].st]=1; cy[pts[i].nd]=1; } int wsk=0; for(auto &i:cx){ X[wsk]=i.st; i.nd=wsk++; } wsk=0; for(auto &i:cy){ Y[wsk]=i.st; i.nd=wsk++; } uint ans=2*INF; X[cx.size()]=h; for(int y=0; y<cy.size(); y++){ for(int i=0; i<cx.size(); i++){ for(int j=0; j<cy.size(); j++){ tim[i][j]=2*INF; } //r[i][wsk]=mp(i, wsk); } Y[cy.size()]=Y[y]+w; deb(y); for(int i=0; i<n; i++){ int xx=cx[pts[i].st]; for(int j=cy[pts[i].nd]; j<cy.size(); j++){ tim[xx][j]=min(tim[xx][j], Y[j+1]-pts[i].nd); } } vector<pair<int, pair<int, int> > > V; for(int i=0; i<cx.size(); i++){ for(int j=0; j<cy.size(); j++){ V.pb(mp(tim[i][j], mp(i, j))); } } sor(V); //for(int x=0; x<cx.size(); x++){ //deb(y); //X[cx.size()]=X[x]+h; for(int x=0; x<cx.size(); x++){ M[x]=0; } for(int i=0; i<cx.size(); i++){ for(int j=0; j<cy.size(); j++){ len[i][j]=X[i+1]-X[i]; if(j>=y){ if(i+1!=cx.size()){ M[i]=max(M[i], len[i][j]); //for(int x=0; x<=i; x++)M[x]=max(M[x], len[i][j]); } else{ //for(int x=0; x<=i; x++)M[x]=max(M[x], len[i][j]+X[x]); } } r[i][j]=mp(i, j); } //r[i][wsk]=mp(i, wsk); } for(int x=cx.size()-1; x>=0; x--){ M[x]=max(M[x], M[x+1]); } for(int j=y; j<cy.size(); j++){ for(int x=0; x<cx.size(); x++){ M[x]=max(M[x], len[cx.size()-1][j]+X[x]); } } vector<int> vx; for(int i=0; i<cx.size(); i++){ vx.pb(i); } for(int i=V.size()-1; i>=0; i--){ if(i+1==V.size() || V[i].st!=V[i+1].st){ uint a=max(Y[y], V[i].st-1); for(int x:vx){ if(ans>a+max(M[x]-1, X[x]))ans=a+max(M[x]-1, X[x]); } } Union(V[i].nd.st, V[i].nd.nd); int xx=r[V[i].nd.st][V[i].nd.nd].st; if(V[i].nd.nd>=y){ uint a=len[r[V[i].nd.st][V[i].nd.nd].st][r[V[i].nd.st][V[i].nd.nd].nd]; if(xx<cx.size()-1){ for(int x:vx){ if(x>xx)break; if(a>M[x])M[x]=a; } } else{ for(int x:vx){ if(x>xx)break; M[x]=max(M[x], min(X[x]+a, (uint)2*INF)); } } //if(M[0]>=2*INF)break; if(i%30==0){ for(int x=0; x<vx.size(); x++){ while(x<vx.size() && M[vx[x]]>=2*INF){ swap(vx[x], vx.back()); vx.pp(); } } sor(vx); } } //deb(x, y, ans); //if(M<INF)ans=min(ans, max(X[x], M)+Y[y]); } } cout<<ans; }

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'int main()':
cultivation.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0; i<pts.size(); i++){
      |               ~^~~~~~~~~~~
cultivation.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int y=0; y<cy.size(); y++){
      |               ~^~~~~~~~~~
cultivation.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0; i<cx.size(); i++){
      |                ~^~~~~~~~~~
cultivation.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(int j=0; j<cy.size(); j++){
      |                 ~^~~~~~~~~~
cultivation.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j=cy[pts[i].nd]; j<cy.size(); j++){
      |                             ~^~~~~~~~~~
cultivation.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i=0; i<cx.size(); i++){
      |                ~^~~~~~~~~~
cultivation.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    for(int j=0; j<cy.size(); j++){
      |                 ~^~~~~~~~~~
cultivation.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for(int x=0; x<cx.size(); x++){
      |                 ~^~~~~~~~~~
cultivation.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for(int i=0; i<cx.size(); i++){
      |                 ~^~~~~~~~~~
cultivation.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int j=0; j<cy.size(); j++){
      |                  ~^~~~~~~~~~
cultivation.cpp:117:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |       if(i+1!=cx.size()){
      |          ~~~^~~~~~~~~~~
cultivation.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |    for(int j=y; j<cy.size(); j++){
      |                 ~^~~~~~~~~~
cultivation.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int x=0; x<cx.size(); x++){
      |                  ~^~~~~~~~~~
cultivation.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |    for(int i=0; i<cx.size(); i++){
      |                 ~^~~~~~~~~~
cultivation.cpp:142:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     if(i+1==V.size() || V[i].st!=V[i+1].st){
      |        ~~~^~~~~~~~~~
cultivation.cpp:152:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |      if(xx<cx.size()-1){
      |         ~~^~~~~~~~~~~~
cultivation.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |      for(int x=0; x<vx.size(); x++){
      |                   ~^~~~~~~~~~
cultivation.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |       while(x<vx.size() && M[vx[x]]>=2*INF){
      |             ~^~~~~~~~~~
#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...