Submission #124526

# Submission time Handle Problem Language Result Execution time Memory
124526 2019-07-03T13:22:33 Z deinfreund Orchard (NOI14_orchard) C++14
13 / 25
544 ms 165404 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, vector<int>(h));
  vector<vector<int>> totalTrees(w, vector<int>(h));
  vector<vector<int> > vals(w, vector<int>(h));
  for (int y = 0; y< h; y++){
    for (int x= 0; x < w; x++){
      cin >> vals[x][y];
      totalTrees[x][y] += vals[x][y];
      if (x > 0) totalTrees[x][y] += totalTrees[x-1][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];
    }
  }
  for (int y = 0; y< h; y++){
    int minv = 0;
    int minx = -1;
    int bests = 0;
    int beste = 0;
    int bestv = 0;
    for (int x= 0; x < w; x++){
      if (sums[x][y] < minv){
	minv = sums[x][y];
	minx = x;
      }
      int v = sums[x][y] - minv;
      if (v > bestv){
	bestv = v;
	bests = minx;
	beste = x;
      }
    }
    //    cout << bests << " - " << beste << ": " << bestv << endl;
    cout << totalTrees[w - 1][y] - 2*(totalTrees[beste][y] - (bests < 0 ? 0 : totalTrees[bests][y])) + beste - bests << 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]
 }
 ^
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 2808 KB Output is correct
2 Correct 11 ms 2680 KB Output is correct
3 Correct 10 ms 2808 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 536 ms 164996 KB Output is correct
2 Correct 535 ms 165200 KB Output is correct
3 Correct 544 ms 165404 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 17052 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 9988 KB Output isn't correct
2 Halted 0 ms 0 KB -