oj.uz

답안 #545824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545824 2022-04-05T14:07:07 Z ivan_tudor Misspelling (JOI22_misspelling) C++14
0 / 100
 1 ms 340 KB 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
const int MOD = 1e9 + 7;
const int SIGMA = 'z' - 'a' + 1;
void add(int &x, long long y){
  y%=MOD;
  x += y;
  if(x >= MOD)
    x-=MOD;
  if(x<0)
    x+=MOD;
}
struct dphelper{
  int nways;
  int lateless;
  int latebig;
};
int lessthan[N];
int bigthan[N];
dphelper dp[N][SIGMA + 1][2][2];
const int INF = -1e9;
int main()
{
  int n, m;
  cin>>n>>m;
  for(int i = 1; i<=m; i++){
    int x, y;
    cin>>x>>y;
    if(x < y)
      bigthan[x] = max(bigthan[x], y);
    if(x > y)
      lessthan[y] = max(lessthan[y], x);;
  }
  dp[0][0][0][0] = {1, INF, INF};
  for(int i = 1; i<=n; i++){
    /// propag pe i - 1, dupa pun restrictiile pt poz i noi si le scot pe cele vechi
    /// propag fara restrictii
    int total_sum = 0;
    for(int let = 0; let <= SIGMA; let++)
      add(total_sum, dp[i - 1][let][0][0].nways);
    for(int let = 1; let <= SIGMA; let++){
      dp[i][let][0][0] = {total_sum, INF, INF};
    }
    total_sum = 0;
    for(int let = 0; let<= SIGMA; let++){
      add(dp[i][let][0][0].nways, total_sum); /// am pus mai mare si am scapat de restrictii
      add(total_sum, dp[i - 1][let][1][0].nways);
      dp[i][let][1][0] = dp[i - 1][let][1][0];
    }

    total_sum = 0;
    for(int let = SIGMA; let>= 1; let--){
      add(dp[i][let][0][0].nways, total_sum); /// am pus mai mic si am scapat de restrictii
      add(total_sum, dp[i - 1][let][0][1].nways);
      dp[i][let][0][1] = dp[i - 1][let][0][1];
    }

    for(int let = 1; let <= SIGMA; let++){
      dp[i][let][1][1] = dp[i - 1][let][1][1];
    }

    /// trb sa reactualizez toate restrictiile
    ///mai intai, anulez ce s a terminat
    for(int let = 1; let<=SIGMA; let++){
        /// de 1 si de 0
        int lless, lbig;

        lless = dp[i][let][1][0].lateless;
        if(lless == i){
          add(dp[i][let][0][0].nways, dp[i][let][1][0].nways);
          dp[i][let][1][0] = {0, INF, INF};
        }

        lbig = dp[i][let][0][1].latebig;
        if(lbig == i){
          add(dp[i][let][0][0].nways, dp[i][let][0][1].nways);
          dp[i][let][0][1] = {0, INF, INF};
        }

        lless = dp[i][let][1][1].lateless;
        lbig = dp[i][let][1][1].latebig;
        if(lless == i && lbig == i){
          add(dp[i][let][0][0].nways, dp[i][let][1][1].nways);
          dp[i][let][1][1] = {0, INF, INF};
        }
        else if(lless == i){
          add(dp[i][let][0][1].nways, dp[i][let][1][1].nways);
          dp[i][let][0][1].latebig = max(dp[i][let][0][1].latebig, lbig);

          dp[i][let][1][1] = {0, INF, INF};
        }
        else if(lbig == i){
          add(dp[i][let][1][0].nways, dp[i][let][1][1].nways);
          dp[i][let][1][0].lateless = max(dp[i][let][1][0].lateless, lless);

          dp[i][let][1][1] = {0, INF, INF};
        }
    }
    /// bag restrictiile noi
    for(int let = 1; let <=SIGMA; let++){
      for(int ls = 0; ls <=1; ls++){
        for(int bg = 0; bg <=1; bg++){
          int newls = ls, newbg = bg;
          if(lessthan[i] > 0)
            newls = 1;
          if(bigthan[i] > 0)
            newbg = 1;
          if(lessthan[i] > 0)
            dp[i][let][newls][newbg].lateless = max(dp[i][let][newls][newbg].lateless, lessthan[i]);
          if(bigthan[i] > 0)
            dp[i][let][newls][newbg].latebig = max(dp[i][let][newls][newbg].latebig, bigthan[i]);
          if((pair<int, int>){ls, bg} != (pair<int, int>){newls, newbg}){
            add(dp[i][let][newls][newbg].nways, dp[i][let][ls][bg].nways);
            dp[i][let][ls][bg] = {0, INF, INF};
          }
        }
      }

    }

  }
  int ans = 0;
  for(int let = 1; let<=SIGMA; let++){
    add(ans, dp[n][let][0][0].nways);
    add(ans, dp[n][let][0][1].nways);
    add(ans, dp[n][let][1][0].nways);
    add(ans, dp[n][let][1][1].nways);
  }
  cout<<ans;
  return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -