oj.uz

Submission #124562

# Submission time Handle Problem Language Result Execution time Memory
124562 2019-07-03T13:53:36 Z deinfreund Orchard (NOI14_orchard) C++14
25 / 25
 605 ms 166392 KB 
#include <bits/stdc++.h>

using namespace std;

int solve1D(vector<int> vals){
  vector<int> sums(vals.size());
  int totalTrees;

  for (int x= 0; x < vals.size(); x++){
    /*cin >> vals[x][y];
      totalTrees[y] += vals[x][y];
      vals[x][y] = 2 * vals[x][y] - 1;
      if (x > 0) sums[x][y] += sums[x-1][y];
      sums[x][y] += vals[x][y];*/
  }
}

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int> > sums(w+1, vector<int>(h+1));
  vector<vector<int>> totalTrees(w+1, vector<int>(h+1));
  vector<vector<int> > vals(w+1, vector<int>(h+1));
  h++;w++;
  for (int y = 1; y< h; y++){
    for (int x= 1; x < w; x++){
      cin >> vals[x][y];
      totalTrees[x][y] += vals[x][y];
      totalTrees[x][y] += totalTrees[x-1][y];
      vals[x][y] = 2 * vals[x][y] - 1;
      sums[x][y] += sums[x-1][y];
      sums[x][y] += vals[x][y];
    }
  }

  for (int x = 0; x < w; x++){
    for (int y = 1; y < h; y++){
      sums[x][y] += sums[x][y - 1];
      totalTrees[x][y] += totalTrees[x][y - 1];
    }
  }
  /*
  for (int y = 0; y < h; y++){
    for (int x = 0; x < w; x++){
      cout << vals[x][y] << " ";
    }
    cout << endl;
  }
  cout << endl;
  for (int y = 0; y < h; y++){
    for (int x = 0; x < w; x++){
      cout << sums[x][y] << " ";
    }
    cout << endl;
  }*/
  int res = 1000000000;
  for (int y1 = 0; y1< h; y1++){
    for (int y2 = y1+1; y2 < h; y2++){
      int minv = 0;
      int minx = 0;
      int bests = 0;
      int beste = 0;
      int bestv = 0;
      for (int x= 0; x < w; x++){
	int s = sums[x][y2] - sums[0][y2] - sums[x][y1] + sums[0][y1];
	if (s < minv){
	  minv = s;
	  minx = x;
	}
	int v = s - minv;
	if (v > bestv){
	  bestv = v;
	  bests = minx;
	  beste = x;
	}
      }
      int val = totalTrees[w - 1][h - 1] - 2*(totalTrees[beste][y2] - totalTrees[bests][y2] - totalTrees[beste][y1] + totalTrees[bests][y1]) + (beste - bests) * (y2 - y1);
      //cout << y1 << " to " << y2 << " " << bests << " to " << beste << " -> "<< val << endl;
      //cout << bestv << endl;
      res = min(res, val);
    }
  }
  cout << res << endl;
}

Compilation message

orchard.cpp: In function 'int solve1D(std::vector<int>)':
orchard.cpp:9:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x= 0; x < vals.size(); x++){
                  ~~^~~~~~~~~~~~~
orchard.cpp:7:7: warning: unused variable 'totalTrees' [-Wunused-variable]
   int totalTrees;
       ^~~~~~~~~~
orchard.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2804 KB Output is correct
2 Correct 10 ms 2808 KB Output is correct
3 Correct 10 ms 2808 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 166136 KB Output is correct
2 Correct 554 ms 166136 KB Output is correct
3 Correct 552 ms 166392 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 17204 KB Output is correct
2 Correct 84 ms 17296 KB Output is correct
3 Correct 84 ms 17144 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 14 ms 632 KB Output is correct
3 Correct 14 ms 632 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 11260 KB Output is correct
2 Correct 601 ms 10752 KB Output is correct
3 Correct 601 ms 10744 KB Output is correct