oj.uz

Submission #130164

# Submission time Handle Problem Language Result Execution time Memory
130164 2019-07-14T06:09:50 Z dragonslayerit Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 2716 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

int N;
char str[100005];
std::vector<int> where[100005];
const char rgy[]="RGY";
char ts[100005];

int main(){
  scanf("%d %s",&N,str);
  for(int i=0;i<N;i++){
    where[std::find(rgy,rgy+3,str[i])-rgy].push_back(i);
  }
  std::copy(str,str+N,ts);
  std::sort(ts,ts+N);
  int best=1e9;
  do{
    int ind[3]={0,0,0};
    int cost=0;
    bool bad=false;
    for(int i=1;i<N;i++){
      if(ts[i]==ts[i-1]) bad=true;
    }
    if(bad) continue;
    for(int i=0;i<N;i++){
      int c=std::find(rgy,rgy+3,ts[i])-rgy;
      cost+=std::max(0,i-where[c][ind[c]++]);
    }
    best=std::min(best,cost);
  }while(std::next_permutation(ts,ts+N));
  printf("%d\n",best<1e9?best:-1);
  return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %s",&N,str);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 10 ms 2680 KB Output is correct
6 Correct 15 ms 2680 KB Output is correct
7 Correct 11 ms 2680 KB Output is correct
8 Correct 15 ms 2712 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Incorrect 10 ms 2680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 10 ms 2680 KB Output is correct
6 Correct 15 ms 2680 KB Output is correct
7 Correct 11 ms 2680 KB Output is correct
8 Correct 15 ms 2712 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Incorrect 10 ms 2680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2600 KB Output is correct
2 Execution timed out 1052 ms 2716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 10 ms 2680 KB Output is correct
6 Correct 15 ms 2680 KB Output is correct
7 Correct 11 ms 2680 KB Output is correct
8 Correct 15 ms 2712 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Incorrect 10 ms 2680 KB Output isn't correct
12 Halted 0 ms 0 KB -