oj.uz

Submission #47971

# Submission time Handle Problem Language Result Execution time Memory
47971 2018-05-09T09:35:34 Z Extazy Calvinball championship (CEOI15_teams) C++17
70 / 100
 16 ms 5816 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1007;
const int MOD = (1e6) + 7;

int n,a[N],pos,cnt,ans;
bool used[N][N];
int state[N][N];

int recurse(int pos, int cnt) {
  if(pos>n) return 1;
  if(used[pos][cnt]) return state[pos][cnt];
  used[pos][cnt]=true;
  return state[pos][cnt]=(recurse(pos+1,cnt+1)+recurse(pos+1,cnt)*1ll*cnt%MOD)%MOD;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;

  scanf("%d", &n);
  for(i=1;i<=n;i++) {
    scanf("%d", &a[i]);
  }

  ans=1;

  cnt=1;
  for(pos=2;pos<=n;pos++) {
    if(a[pos]>cnt) {
      ans+=recurse(pos+1,cnt)*1ll*cnt%MOD;
      ans%=MOD;
      
      ++cnt;
    }
    else {
      ans+=recurse(pos+1,cnt)*1ll*(a[pos]-1)%MOD;
      ans%=MOD;
    }
  }

  printf("%d\n", ans);

  return 0;
}

Compilation message

teams.cpp: In function 'int main()':
teams.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
teams.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 2 ms 660 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 728 KB Output is correct
3 Correct 2 ms 864 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1168 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3232 KB Output is correct
2 Correct 6 ms 3236 KB Output is correct
3 Correct 6 ms 3236 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5804 KB Output is correct
2 Correct 16 ms 5808 KB Output is correct
3 Correct 15 ms 5812 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 5816 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5816 KB Output isn't correct
2 Halted 0 ms 0 KB -