oj.uz

답안 #100679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100679 2019-03-13T07:24:26 Z pzdba Mobitel (COCI19_mobitel) C++14
130 / 130
 2111 ms 5624 KB 
#include <bits/stdc++.h>
using namespace std;
int mod = 1000000007;
int a[305][305];
int dp[2][2][305][1005];
int add(int a, int b){
    return (a+b)%mod;
}
int main(){
    int r, c, n;
    scanf("%d%d%d", &r, &c, &n);
    for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d", &a[i][j]);
    if(n <= 1000){
        int pv = 0, nt = 1;
        for(int i=2;i<=r+c;i++){
            memset(dp[nt][0], 0, sizeof(dp[nt][0]));
            memset(dp[nt][1], 0, sizeof(dp[nt][1]));
            for(int y=1;y<=r;y++){
                int x = i-y;
                if(y > r || x > c || y < 1 || x < 1) continue;
                if(i == 2){
                    if(a[y][x] >= n) dp[nt][0][y][n] = add(dp[nt][0][y][n], 1);
                    else dp[nt][0][y][a[y][x]] = add(dp[nt][0][y][a[y][x]], 1);
                }
                else{
                    for(int j=1;j<=n;j++){
                        int k = j*a[y][x];
                        if(k >= n){
                            dp[nt][0][y][n] = add(dp[nt][0][y][n], dp[pv][0][y][j]);
                            if(y-1 >= 1) dp[nt][0][y][n] = add(dp[nt][0][y][n], dp[pv][0][y-1][j]);
                        }
                        else{
                            dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y][j]);
                            if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y-1][j]);
                        }
                    }
                }
            }
            swap(pv, nt);
        }
        printf("%d\n", dp[pv][0][r][n]);
    }
    else{
        int pv = 0, nt = 1;
        for(int i=2;i<=r+c;i++){
            memset(dp[nt][0], 0, sizeof(dp[nt][0]));
            memset(dp[nt][1], 0, sizeof(dp[nt][1]));
            for(int y=1;y<=r;y++){
                int x = i-y;
                if(y > r || x > c || y < 1 || x < 1) continue;
                if(i == 2){
                    if(a[y][x] >= n) dp[nt][1][y][1] = add(dp[nt][1][y][1], 1);
                    else{
                        int k = a[y][x];
                        if(a[y][x] > 1000){
                            k = (n+k-1)/k;
                            dp[nt][1][y][k] = add(dp[nt][1][y][k], 1);
                            if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], 1);
                        }
                        else{
                            dp[nt][0][y][k] = add(dp[nt][0][y][k], 1);
                            if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], 1);
                        }
                    }
                }
                else{
                    for(int j=1;j<=1000;j++){
                        int k = j*a[y][x];
                        if(k > 1000){
                            k = (n+k-1)/k;
                            dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][0][y][j]);
                            if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][0][y-1][j]);
                        }
                        else{
                            dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y][j]);
                            if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y-1][j]);
                        }
                    }
                    for(int j=1;j<=1000;j++){
                        int k = (j+a[y][x]-1)/a[y][x];
                        dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][1][y][j]);
                        if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][1][y-1][j]);
                    }
                }
            }
            swap(pv, nt);
        }
        printf("%d\n", dp[pv][1][r][1]);
    }
}

Compilation message

mobitel.cpp: In function 'int main()':
mobitel.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &r, &c, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:12:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d", &a[i][j]);
                                                 ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
130.0 / 130.0

# 결과 실행 시간 메모리 Grader output
1 Correct 422 ms 5624 KB Output is correct
2 Correct 354 ms 5504 KB Output is correct
3 Correct 235 ms 5248 KB Output is correct
4 Correct 267 ms 5248 KB Output is correct
5 Correct 283 ms 5368 KB Output is correct
6 Correct 265 ms 5368 KB Output is correct
7 Correct 149 ms 5248 KB Output is correct
8 Correct 1154 ms 5504 KB Output is correct
9 Correct 2111 ms 5504 KB Output is correct
10 Correct 1944 ms 5624 KB Output is correct