Submission #534988

#	Time	Username	Problem	Language	Result	Execution time	Memory
534988		79brue	Lamps (JOI19_lamps)	C++14	100 / 100	246 ms	27764 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
bool a[1000002];
bool b[1000002];
int DP[1000002][3][2]; /// 0 1 ? / 0101 1010

bool diff(int i, int x, int y){
    return b[i-1]==x && b[i]!=y;
}

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

    for(int i=0; i<=n; i++) for(int j=0; j<3; j++) for(int k=0; k<2; k++) DP[i][j][k] = 1e9;
    DP[0][2][0] = 0;

    for(int i=1; i<=n; i++){
        for(int j=0; j<2; j++){
            for(int k=0; k<2; k++){
                DP[i][j][k] = min(DP[i][j][k], DP[i-1][j][k] + diff(i, j, j));
                DP[i][j][k] = min(DP[i][j][k], DP[i-1][!j][k] + diff(i, !j, j) + (j!=k));
                if(j==k) DP[i][j][k] = min(DP[i][j][k], DP[i-1][2][0] + diff(i, a[i-1], j) + 1);

                DP[i][2][0] = min(DP[i][2][0], DP[i-1][j][k] + diff(i, j, a[i]));
//                printf("%d %d %d: %d\n", i, j, k, DP[i][j][k]);
            }
        }
        DP[i][2][0] = min(DP[i][2][0], DP[i-1][2][0] + diff(i, a[i-1], a[i]));
//        printf("%d %d %d: %d\n", i, 2, 0, DP[i][2][0]);
    }

    int ans = 1e9;
    for(int i=0; i<3; i++) for(int j=0; j<2; j++) ans = min(ans, DP[n][i][j]);
    printf("%d", ans);
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:18:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
   18 |     for(int i=1; i<=n; i++) scanf("%1d", &a[i]);
      |                                    ~~^   ~~~~~
      |                                      |   |
      |                                      |   bool*
      |                                      int*
lamp.cpp:19:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
   19 |     for(int i=1; i<=n; i++) scanf("%1d", &b[i]);
      |                                    ~~^   ~~~~~
      |                                      |   |
      |                                      |   bool*
      |                                      int*
lamp.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
lamp.cpp:18:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for(int i=1; i<=n; i++) scanf("%1d", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~~
lamp.cpp:19:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1; i<=n; i++) scanf("%1d", &b[i]);
      |                             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49