Submission #585330

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
585330	2022-06-28 16:37:45	Ace	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	154 ms	122784 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2;
const int L = 1e3;
const ll MOD = 1e9+7;
ll dmod(ll x){
  return x%MOD;
}
int n,l;
int a[N+5];
int memo[N+2][N+2][L+2][3];
int dp(int x, int cc, int sisa, int tepi){
  if(sisa < 0) return 0;
//  printf(">> %d %d %d %d\n", x, cc, sisa, tepi);
  if(x > n){
    if(tepi == 2 && cc == 1) return 1;
    return 0;
  }
  if(tepi == 2 && cc == 1) return 0;
  int &ret = memo[x][cc][sisa][tepi];
  if(ret != -1) return ret;
  ret = 0;
  // nambah cc
  ret = dmod(ret + dmod((ll)(cc+1ll - tepi) * dp(x+1,cc+1,sisa-(2*(cc+1) - tepi)*(a[x+1]-a[x]),tepi)));
  if(tepi < 2) ret = dmod(ret + dmod((ll)(2ll-tepi)*dp(x+1,cc+1,sisa-(2*(cc+1) - tepi - 1)*(a[x+1]-a[x]),tepi+1)));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80