akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 1000000007
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;
bool f=0;
ll r;
ll ppow(ll a,ll b,ll m)
{
    ll res=1;
    while(b>0)
    {
        if(b&1)res=(res*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return res;
}
ll gcdExtended(ll a, ll b, ll *x, ll *y); 
  
// Function to find modulo inverse of b. It returns 
// -1 when inverse doesn't 
ll modInverse(ll b, ll m) 
{ 
    ll x, y; // used in extended GCD algorithm 
    ll g = gcdExtended(b, m, &x, &y); 
  
    // Return -1 if b and m are not co-prime 
    if (g != 1) 
        return -1; 
  
    // m is added to handle negative x 
    return (x%m + m) % m; 
} 
  
// Function to compute a/b under modlo m 
void modDivide(ll a, ll b, ll m) 
{ 
    a = a % m; 
    ll inv = modInverse(b, m); 
    if (inv == -1)return; 
       //cout << "Division not defined"; 
    else
    {
       //cout << "Result of division is " << (inv * a) % m; 
       r=(inv * a) % m; 
       f=1;
       //exit(0);
    	return;
    }
} 
  
// C function for extended Euclidean Algorithm (used to 
// find modular inverse. 
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    ll x1, y1; // To store results of recursive call 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
} 
void solve()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	vi r;
	int f=0;
	forn(i,n)
	{
		if(s[i]=='W')f=1;
		if(s[i]=='R'&&f)r.pb(i);
	}

	int p=0;
	int ans=0;
	reverse(all(r));
	for(auto i:r)
	{
		while(s[p]=='R')p++;
		if(p<i)
		{
			swap(s[p],s[i]);
			ans++;
		}
	}
	cout<<ans<<endl;
	
}
int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    int t=1;
    //cin>>t;
   // seive();
    while(t--)
	solve();
    return 0;
}

Measured memory_bytes: 4304
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, sum, res, in, out;
    std::scanf("%d", &n);
    std::scanf("%d", &sum);
    res = sum;
    for (int i = 0; i < n; i++) {
        std::scanf("%d %d", &in, &out);
        if (sum >= 0) {
            sum += (in - out);
            res = max(res, sum);
        }
    }
    (sum < 0) ? printf("%d\n", 0) : printf("%d\n", res);
    return 0;
}



Measured memory_bytes: 2756
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  std::vector<std::pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    int b;
    std::cin >> b;
    a.at(i) = {b, i + 1};
  }

  std::sort(a.begin(), a.end());

  for (auto it = a.begin(); it != a.end(); ++it) {
    if (it != a.begin())
      std::cout << " ";
    std::cout << it->second;
  }
  std::cout << std::endl;
}


Measured memory_bytes: 1664
import sys
import fractions


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    ls = [[0] * (n + 1) for _ in range(2)]
    for i in range(1, n + 1):
        ls[0][i] = fractions.gcd(ls[0][i-1], a[i-1])
        ls[1][-i-1] = fractions.gcd(ls[1][-i], a[-i])
    mt = 0
    for i in range(n):
        mt = max(mt, fractions.gcd(ls[0][i], ls[1][i+1]))
    print(mt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 83820
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) throws Exception {

        int[] iNum = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1,
                51 };

        Scanner sc = new Scanner(System.in);
        int iNext = sc.nextInt();

        int iResult = iNum[iNext - 1];
        System.out.print(iResult);
    }
}


Measured memory_bytes: 35660
#include <bits/stdc++.h>

using namespace std;

int maxx(int a, int b, int c){
    if(a > b && a > c)
        return a;
    else if(b > c)
        return b;
    else 
        return c;
}

int pos_maxx(int a, int b, int c){
    if(a > b && a > c)
        return 0;
    else if(b > c)
        return 1;
    else 
        return 2;
}

int main(){
    int n;
    cin >> n;
    int a[n][3];
    for(int i = 0; i<n ;i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    
    int dp1[n][3], dp2[n][3];
    dp1[0][0] = a[0][0];
    dp1[0][1] = a[0][1];
    dp1[0][2] = a[0][2];
    for(int i = 1;i<n;i++){
        for(int j = 0; j<3; j++){
            dp1[i][j] = max(dp1[i-1][(j+1)%3], dp1[i-1][(j+2)%3]) + a[i][j];
        }
    }
    dp2[n-1][0] = a[n-1][0];
    dp2[n-1][1] = a[n-1][1];
    dp2[n-1][2] = a[n-1][2];
    for(int i = n-2;i>=0;i--){
        for(int j = 0; j<3; j++){
            dp2[i][j] = max(dp2[i+1][(j+1)%3], dp2[i+1][(j+2)%3]) + a[i][j];
        }
    }
    //cout << endl;


    // for(int i = 0; i<n; i++)
    //     // for(int j = 0; j<3; j++)
    //         cout << dp1[i][0] << " " << dp1[i][1] << " " << dp1[i][2] << endl;
    
    // cout << endl;

    // for(int i = 0; i<n; i++)
    //     // for(int j = 0; j<3; j++)
    //         cout << dp2[i][0] << " " << dp2[i][1] << " " << dp2[i][2] << endl;

    // cout << endl;
    
    int max = 0;
    for(int i = 0;i<n;i++)
        for(int j = 0; j<3; j++){
            if(max < dp1[i][j]+dp2[i][j] - a[i][j])
                max = dp1[i][j]+dp2[i][j] - a[i][j];
        }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 3712
X, N = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

ans = X

for i in range(0,101):
        if (X - i) not in P:
                ans = X - i
                break
        elif (X + i) not in P:
                ans = X + i
                break
print(ans)

Measured memory_bytes: 9184
import sys
import numpy as np

# H N モンスターの体力と必殺技の数
h, n = map(int, input().split())

# A1... 必殺技の与えるダメージ
a = list(map(int, input().split()))

for i in a:
    h -= i

if h > 0:
    # 倒せない
    print("No")
else:
    # 倒せる
    print("Yes")

Measured memory_bytes: 23012
def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if y == 0:
        return x
    return gcd(y, x % y)
N = int(input())
A = list(map(int, input().split()))
B = [A[0]] * N
C = [A[N - 1]] * N
for i in range(N - 1):
    B[i + 1] = gcd(B[i], A[i + 1])
    C[N - i - 2] = gcd(C[N - i - 1], A[N - i - 2])
ans = max(B[N - 2], C[1])
for i in range(N - 2):
    ans = max(ans, gcd(B[i], C[i + 2]))
print(ans)

Measured memory_bytes: 64108
#include<bits/stdc++.h>
#define int long long
#define REP(i,a,n) for(int i=a;i<(n);i++)
#define RE return
#define FILL(a,b) memset(a,b,sizeof(a))
#define SO(a) sort(all(a))
#define pb push_back
#define sz(a) a.size()
#define V vector
#define ld long double
#define viit(a) vector<int>::iterator a
#define IT iterater
#define FOR(i,a,n) for(int i=a;i<=(n);i++)
#define B(s) s.back()
#define all(a) a.begin(),a.end()
#define ER1(a) a.erase(a.begin())
#define ER0(a) a.erase(a.end())
#define pii pair<int,int>
#define pause system("PAUSE")
#define cls system("CLS")
using namespace std;
signed main()
{
	int n,sum=0,x,y;
	int d;
	cin>>n>>d;
	d*=d;
	while(n--){
		cin>>x>>y;
		if(x*x+y*y<=d)sum++;
	}
	cout<<sum;
    return 0;
}


Measured memory_bytes: 3584
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans
    
    ### intチェック
    def is_integer(self, n):
        try:
            float(n)
        except ValueError:
            return False
        else:
            return float(n).is_integer()

    ### 幾何学問題用
    def dist(self, A, B):
        d = 0
        for i in range(len(A)):
            d += (A[i]-B[i])**2            
        d = d**(1/2)
        return d

    ### 絶対値
    def abs(self, n):
        if n >= 0:
            return n
        else:
            return -n   

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

def printA(A):
    N = len(A)
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート（代入する必要なし）
# N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def get_input():
    N = []
    while True:
        try:
            #N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
            N.append([int(x) for x in input().split()])
        except EOFError:
            break
    return N

#D = get_input()

s = input()

print(str.upper(s))



Measured memory_bytes: 5660
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N, C; cin >> N >> C;
    struct Program
    {
        int S; int T; int C;
        const bool operator<(const Program &rhs)
        {
            if (S != rhs.S) return S < rhs.S;
            else return C < rhs.C;
        }
    };
    map<int, vector<pair<int, int>>> C2SandTMap;
    for (int i = 0; i < N; ++i)
    {
        int si, ti, ci; cin >> si >> ti >> ci;
        C2SandTMap[ci].push_back({ si, ti });
    }
    // 同じチャンネルで，ti = sjとなるものは必ず連続して撮る方が最適
    vector<Program> programs;
    for (int c = 1; c <= C; ++c)
    {
        if (C2SandTMap.find(c) != C2SandTMap.end())
        {
            auto STpairs = C2SandTMap[c];
            sort(STpairs.begin(), STpairs.end());
            int pairNum = static_cast<int>(STpairs.size());
            int si = STpairs[0].first, ti = STpairs[0].second;
            for (int j = 1; j < pairNum; ++j)
            {
                if (ti == STpairs[j].first)
                {
                    ti = STpairs[j].second;
                }
                else
                {
                    programs.push_back({ si, ti, c });
                    si = STpairs[j].first;
                    ti = STpairs[j].second;
                }
            }
            programs.push_back({ si, ti, c });
        }
    }
    sort(programs.begin(), programs.end());
    // 開始時刻が早い順に積んでいく
    multiset<int> endTimeSet;   //  終了時刻が早い順にソートしておく
    endTimeSet.insert(-programs.front().T); // upper_boundを降順で使うために-1を掛けておく
    int pNum = static_cast<int>(programs.size());
    for (int i = 1; i < pNum; ++i)
    {
        const int si = -programs[i].S;  // upper_boundを降順で使うために-1を掛けておく
        const int ti = -programs[i].T;  // upper_boundを降順で使うために-1を掛けておく
        auto itr = upper_bound(endTimeSet.begin(), endTimeSet.end(), si);
        if (itr == endTimeSet.end())
        {
            endTimeSet.insert(ti);
        }
        else
        {
            endTimeSet.erase(itr);
            endTimeSet.insert(ti);
        }
    }
    int ans = static_cast<int>(endTimeSet.size());
    cout << ans << endl;
}


Measured memory_bytes: 3128
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
int a[N] , n;
unordered_map <int,int> mp;
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    long long ans = 0;
    for (int i = 1; i <= n; i++){
        if (i > a[i]) ans = ans + mp[i - a[i]]; // get result at [i]
        mp[a[i] + i]++; // update result at [i]
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 12764
#include<bits/stdc++.h>
#include<sstream>

#define ll long long

using namespace std;


int main(){
    int N;
    string S, T;
    cin >> N;
    cin >> S >> T;
    string str;
    for(int i = 0; i < N; i++){
        str = str + S[i] + T[i];
    }
    cout << str << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdexcept>
#include <cassert>
#include <vector>
using namespace std;


int getSum(vector<vector<int>>& c, vector<vector<bool>>& isRed, int H, int W) {
  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (c[i][j] == 1 && !isRed[i][j]) ans++;
  }}
  return ans;
}


long long dfs(vector<vector<int>>& c, vector<vector<bool>> isRed, int H, int W, int K, int cur) {
  if (cur >= H + W) {
    if (getSum(c, isRed, H, W) == K) {
      // cout << "This red pattern counts!" << endl;
      // for (int i = 0; i < H; i++) {
      //   for (int j = 0; j < W; j++) {
      //     cout << isRed[i][j];
      //   }
      //   cout << endl;
      // }
      // cout << endl;
      return 1;
    } else return 0;
  } else if (cur < H) {
    int i = cur;
    long long ans = 0;
    ans += dfs(c, isRed, H, W, K, cur + 1);
    for (int j = 0; j < W; j++) isRed[i][j] = true;
    ans += dfs(c, isRed, H, W, K, cur + 1);
    return ans;
  } else {
    int j = cur - H;
    long long ans = 0;
    ans += dfs(c, isRed, H, W, K, cur + 1);
    for (int i = 0; i < H; i++) isRed[i][j] = true;
    ans += dfs(c, isRed, H, W, K, cur + 1);
    for (int i = 0; i < H; i++) isRed[i][j] = false;
    return ans;
  }
}


int main() {
  int H, W, K;
  cin >> H >> W >> K;

  vector<vector<int>> c(H, vector<int> (W, 0));
  char cell;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> cell;
      if (cell == '#') c[i][j] = 1;
    }
  }
  vector<vector<bool>> isRed(H, vector<bool> (W, false));
  long long ans = dfs(c, isRed, H, W, K, 0);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;

# define REP(i,n) for (int i=0;i<(n);++i)
# define PER(i,n) for (int i=(N-1);i>=0;--i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<P_ii> a(N);
    REP(i, N) cin >> a[i].first >> a[i].second; 
    sort(all(a));

    priority_queue<P_ii> pque;
    int now = 1;
    int i = 0;
    ll ans = 0;
    while(1) {
        while(i < N){
            if(a[i].first <= now) {
                pque.push(make_pair(a[i].second,a[i].first));
                i++;
            } else {
                break;
            }
        }

        if(!pque.empty()) {
            auto p = pque.top();
            pque.pop();

            ans += 1LL * p.first;
        }

        if(now == M) break;
        now++;
    }

    pl(ans)

    return 0;
}


Measured memory_bytes: 3956
#

import sys
input=sys.stdin.readline

def main():
    ab="qwertyuiopasdfghjklzxcvbnm"
    S=input()
    y=1
    for a in ab:
        if S.count(a)>1:
            y=0
            break
    if y==1:
        print("yes")
    else:
        print("no")
    
if __name__=="__main__":
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 1;
    for(int i = 1; i < S.size(); i++){
        if(S[i-1] != S[i]){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
def main():


    #Union Find

    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]

    n,m = map(int,input().split())
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*n

    for i in range(m):
        a,b = map(int,input().split())
        unite(a-1,b-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    #print(tank)
    print(len(tank)-1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 78544
from collections import defaultdict

N, M = map(int, input().split())
H = list(map(int, input().split()))

edge = defaultdict(list)

for i in range(M):
    a, b = map(int, input().split())
    edge[a - 1].append(H[b - 1])
    edge[b - 1].append(H[a - 1])

ans = 0
for i in range(N):
    if len(edge[i]) == 0 or H[i] > max(edge[i]):
        ans += 1

print(ans)

Measured memory_bytes: 33232
#include <bits/stdc++.h>

#define ll long long 
#define ull unsigned long long
#define all(c) c.begin(),c.end()
#define pb push_back

const ll INF = 1e9+5;

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<int>a(n+1),b(n+1),c(n+1);
	for(int i = 1 ; i <= n ;++i ){
		cin >> a[i] >> b[i] >> c[i];
	}
	ll dp[n+1][3];
	a[0]=b[0]=c[0]=0;
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i = 1 ; i <= n ; ++i){
		dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
		dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]=c[i]+max(dp[i-1][1],dp[i-1][0]);
	}

	cout << max(dp[n][1],max(dp[n][0],dp[n][2])) << endl;
	return 0;
}

Measured memory_bytes: 3840
//~#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//~#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//~#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;
//~#define int ll
#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=200005;

int dp[405][405];

int interpolate(int x,int pw){
	if(pw==0){
		return x;
	}
	if(x<pw+2){
		return dp[pw][x];
	}
	int lst=1;
	for(int i=1;i<pw+2;i++){
		lst=mul(lst,(x-i+mod)%mod);
		lst=mul(lst,powz((mod-i)%mod,mod-2));
	}
	int ans=0;
	add(ans,mul(dp[pw][0],lst));
	for(int i=1;i<pw+2;i++){
		lst=mul(lst,(x-(i-1)+mod)%mod);
		lst=mul(lst,(i-1-(pw+1)+mod)%mod);
		lst=mul(lst,powz((x-i+mod)%mod,mod-2));
		lst=mul(lst,powz(i,mod-2));
		add(ans,mul(dp[pw][i],lst));
	}
	return ans;
}

int dp4[2][405];
int dp3[405][405];

void solve(){
	for(int i=1;i<=400;i++){
		int cr=0;
		for(int j=0;j<=402;j++){
			add(cr,powz(j,i));
			dp[i][j]=cr;
		}
	}
	int n,c;
	cin>>n>>c;
	vector<int>a(n);
	cin>>a;
	vi b(n);
	cin>>b;
	dp4[0][0]=1;
	for(int i=0;i<n;i++){
		for(int put=0;put<=c;put++){
			for(int left_set=0;left_set<=c-put;left_set++){
				if(left_set==0){
					add(dp4[1][put+left_set],mul(dp4[0][put],b[i]-a[i]+1));
				}
				else{
					add(dp4[1][put+left_set],mul(dp4[0][put],(dp[left_set][b[i]]-dp[left_set][a[i]-1]+mod)%mod));
				}
			}
		}
		for(int put=0;put<=c;put++){
			dp4[0][put]=dp4[1][put];
			dp4[1][put]=0;
		}
	}
	cout<<dp4[0][c];
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //~cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}



Measured memory_bytes: 896
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int a[4];

int main()
{
    string s;
    cin >> s;
    rep(i, s.size()) {
        if(s[i] == 'N') {
            a[0]++;
        }
        else if(s[i] == 'S') {
            a[1]++;
        }
        else if(s[i] == 'E') {
            a[2]++;
        }
        else a[3]++;
    }
    string ans = "Yes";
    if(a[0]!= 0) {
        if(a[1] == 0) ans = "No";
    }
    if(a[1]!= 0) {
        if(a[0] == 0) ans = "No";
    }
    if(a[2]!= 0) {
        if(a[3] == 0) ans = "No";
    }
    if(a[3]!= 0) {
        if(a[2] == 0) ans = "No";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;


//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int a, b, c;
	cin>>a>>b>>c;

	cout << b*a/2 << endl;

}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        x: i64,
        a: i64,
        b: i64,

    }
    println!("{}", if (a-x).abs() < (b-x).abs() {"A"} else {"B"});
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
using namespace std;

int main(){
  int a,b;
  while(cin >> a >> b,a){
    int s,m,l;
    int tmp = b-a;

    l = tmp/1000;
    tmp = tmp%1000;
    m = tmp/500;
    tmp = tmp%500;
    s = tmp/100;

    cout << s << " " << m << " " << l << endl;
  }
  return 0;
}


Measured memory_bytes: 3040
def main():
  N, K = map(int, input().split())
  N = N + 1
  A=[n for n in range(N)]
  S=[0]*(N+1)
  for a in A:
    S[a+1]+=S[a]+a
  ans=0
  for k in range(K, N+1):
    maxS, minS=S[-1], S[k]
    offset=S[-k-1]
    ans+=(maxS - offset) - minS + 1
  print(ans%(1000000007))
  
if __name__=='__main__':
  main()

Measured memory_bytes: 27228
import numpy as np
N = int(input())
dp = np.zeros(N+1, dtype=np.float64)
p_lst = list(map(float, input().split()))
dp[0] = 1
for p in p_lst:
  next_dp = dp * (1-p)
  next_dp[1:] += dp[:-1] * p
  dp = next_dp

print(dp[N//2+1:].sum())

Measured memory_bytes: 27572
import java.io.*;
import java.util.*;

public class Main{ 
	public static void main(String args[]) throws IOException{
		Scanner scr = new Scanner(System.in);
		while (true){
		    try{
				int n = Integer.parseInt(scr.nextLine());
				if (n==0) break; //??\?????????
				System.out.println( SearchGrab(n) );
			}catch(Exception e){
				System.err.println("Exception");
				break;
			}
        }
		scr.close();
	}
	
	
	private static int SearchGrab(int n){
		int m = Integer.MAX_VALUE;
		for(int z=0; z*z*z<=n; z++){
			int z3 = z*z*z;
			for(int y=0; y*y<=n-z3; y++){
				int x = n - z3 - y*y;
				if(x+y+z<m) m=x+y+z;				
			}
		}
		return m;
	}
}

Measured memory_bytes: 41584
#include <bits/stdc++.h>

#define debug(x) cout << #x" = " << x;

#define st first
#define nd second

using namespace std;
using namespace placeholders;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int MAXN = 1E5 + 10;

int a[MAXN];

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for (int x, i = 0; i < 2 * m; ++i)
		scanf("%d", &x), a[x - 1] ^= 1;
	puts(accumulate(a, a + n, 0) ? "NO" : "YES");
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n >> s;
    int ans=1;

    for(int i=0;i<n-1;i++){
        if(s.at(i)!=s.at(i+1))ans++;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
using namespace std;

int getSumOfDigits(int n){
    int sum = 0;
    while(n>0){
        int digit = n % 10;
        sum = sum + digit;
        n = n / 10;
    }
    return sum;
}

int main(void){
    int n,a,b,sum,total=0;
    cin >> n >> a >> b;
    for(int i=0;i<=n;i++){
        int sum = getSumOfDigits(i);
        if(a<=sum && sum<=b) total = total + i;
    }
    cout << total << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    unsigned long long ans = 0;
    for(int i = 0; i < n; ++i) cin >> a[i];
    
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 3892
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
	int a[4],ans=LONG_LONG_MIN;
	cin>>a[0]>>a[1]>>a[2]>>a[3];
	for(int i=0;i<4;i++)
	for(int j=i+1;j<4;j++)
	{
		if(j==1&&i==0)continue;
		if(j==3&&i==2)continue;
		ans=max(ans,a[j]*a[i]);
	}
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3640
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
c = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        c[j] += i - b[j] if a[i] >> j & 1 else b[j]
        b[j] += a[i] >> j & 1
for j in range(60):
    ans += c[j] << j
    ans %= 10**9 + 7
print(ans)


Measured memory_bytes: 136388
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct edge {
	int to, cap, rev;
	edge(int t, int c, int r):to(t), cap(c), rev(r){}
};

int n, m;
int s, t;

vector<vector<edge> > G;
vector<int> level;
vector<int> iter;
constexpr int INF = 0xfffffff;

void init(int V) {
	G.assign(V, vector<edge>());
	level.assign(V, 0);
	iter.assign(V, 0);
}

void add_edge(int from, int to, int cap) {
	G[from].push_back(edge(to, cap, G[to].size()));
	G[to].push_back(edge(from, 0, G[from].size() - 1));
}

void bfs(int s) {
	fill(level.begin(), level.end(), -1);
	queue<int> que;
	level[s] = 0;
	que.push(s);

	while(!que.empty()) {
		const int v = que.front();
		que.pop();

		for(int i = 0; i < (int)G[v].size(); ++i) {
			const edge& e = G[v][i];
			if(e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v, int t, int f) {
	if(v == t)
		return f;

	for(int& i = iter[v]; i < (int)G[v].size(); ++i) {
		edge& e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]) {
			const int d = dfs(e.to, t, min(f, e.cap));
			if(d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return 0;
}

int max_flow(int a, int b) {
	int flow = 0;
	vector<vector<edge>> tmp(G);
	add_edge(a + n, t, 1);
	add_edge(b + n, t, 1);

	for(;;) {
		bfs(s);
		if(level[t] < 0) {
			G.swap(tmp);
			return flow;
		}

		fill(iter.begin(), iter.end(), 0);
		int f;
		while((f = dfs(s, t, INF)) > 0) {
			flow += f;
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> m;

	init(n + n + 1);
	s = n;
	t = n + n;

	for(int i = 0; i < n; ++i) {
		add_edge(i, i + n, 1);
	}

	for(int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;

		cout << (max_flow(a, b) == 2 ? "Yes" : "No") << endl;
		add_edge(a + n, b, 1);
		add_edge(b + n, a, 1);
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1704
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int inf = 1<<20;
const int dxs[] = {-1, 0, 1, 0};
const int dys[] = {0, 1, 0, -1};

void calc_memo(vector<vector<int> > &wall, vector<int> &memo)
{
	const int h = wall.size();
	const int w = wall[0].size();

	for(int sx = 0; sx < h; ++sx) {
		for(int sy = 0; sy < w; ++sy) {
			for(int wd = 0; wd < 4; ++wd) {

				vector<int> dist(h * w, inf);
				queue<pair<int, int> > q;

				q.push(make_pair(sx, sy));
				dist[sx * w + sy] = 0;

				while(!q.empty()) {

					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					for(int dir = 0; dir < 4; ++dir) {

						int dx = dxs[dir], dy = dys[dir];
						int nx = dx + x, ny = dy + y;
						bool ok = ((1 << dir) & wall[x][y]) == 0;
						if(x == sx && y == sy && wd == dir)
							ok = false;

						if(!ok)
							continue;
						if(nx < 0 || nx >= h || ny < 0 || ny >= w)
							continue;
						if(dist[nx * w + ny] < inf)
							continue;
						dist[nx * w + ny] = dist[x * w + y] + 1;
						q.push(make_pair(nx, ny));
					}
				}

				memo[(sx * w + sy) * 4 + wd] = dist[w * h - 1];
				//printf("debug calc_memo: %d %d %d -> %d (%d)\n", sx, sy, wd, dist[w * h - 1], wall[sx][sy] & (1<<wd));
			}
		}
	}
}

bool check(int card, vector<vector<int> > &wall, vector<int> &memo)
{
	const int h = wall.size();
	const int w = wall[0].size();
	vector<int> dist(h * w, inf);
	queue<pair<int, int> > q;

	q.push(make_pair(0, 0));
	dist[0] = 0;

	//printf("debug: check %d\n", card);

	while(!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int d = dist[x * w + y];

		for(int dir = 0; dir < 4; ++dir) {

			int nx = x + dxs[dir], ny = y + dys[dir];
			bool ok = ((1 << dir) & wall[x][y]) == 0;

			if(!ok)
				continue;
			if(nx < 0 || nx >= h || ny < 0 || ny >= w)
				continue;
			if(d + memo[(x * w + y) * 4 + dir] > card)
				continue;
			if(dist[nx * w + ny] < inf)
				continue;

			//printf("debug: %d %d %d -> %d %d\n", x, y, dir, d, memo[(x*w+y)*4+dir]);
			dist[nx * w + ny] = d + 1;
			q.push(make_pair(nx, ny));
		}
	}


	return dist[w * h - 1] < inf;
}

int main()
{
	while(true) {

		int h, w;
		vector<vector<int> > wall;

		scanf("%d%d", &h, &w);
		if(h == 0)
			break;

		wall.resize(h);
		for(int i = 0; i < h; ++i)
			wall[i].resize(w, 15);

		for(int i = 0; i < h * 2 - 1; ++i) {
			for(int j = 0; j < (i % 2 == 0 ? w - 1 : w); ++j) {

				int t;
				scanf("%d", &t);

				if(t == 1)
					continue;

				if(i % 2 == 0)
					wall[i / 2][j] ^= 2, wall[i / 2][j + 1] ^= 8;
				if(i % 2 == 1)
					wall[i / 2][j] ^= 4, wall[i / 2 + 1][j] ^= 1;
			}
		}

		vector<int> memo(w*h*4);

		calc_memo(wall, memo);

		int lb = 0, ub = inf;

		while(ub - lb > 1) {
			int mid = (lb + ub) / 2;
			if(check(mid, wall, memo))
				ub = mid;
			else
				lb = mid;
		}

		int ans = ub < inf ? ub : -1;
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 1080
#include<bits/stdc++.h>
typedef long long ll;
typedef std::pair<ll,ll> P;

#define rep(i,n) for(int i = 0; i < int(n); i++)
using namespace std;



template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

class modint {
	static constexpr std::int_fast64_t Modulus = 1e9 + 7;
	using u64 = std::int_fast64_t;

public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const ll rhs) const noexcept {
		return modint(*this) *= modint(rhs);
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr operator u64() const { return a; }
};

ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return abs(a); }

int main() {
	ll h, w, d;
	cin >> h >> w >> d;
	vector<vector<int>> grid(h, vector<int>(w, 0));
	vector<P> p(h * w + 1);
	rep(i, h) {
		rep(j, w) {
			cin >> grid[i][j];
			p[grid[i][j]] = { i, j };
		}
	}
	map<int, vector<ll>> memo;
	for (int i = 1; i <= min(h * w, d); i++) {
		memo[i].push_back(0);
		for (int j = 0; i + d * (j+1) <= h * w; j++) {
			auto pos = p[i + d * j];
			auto pos2 = p[i + d * (j+1)];
			auto dx = pos.first - pos2.first;
			auto dy = pos.second - pos2.second;
			auto prev = memo[i].back();
			memo[i].push_back(prev + abs(dx) + abs(dy));
		}
	}
	ll q;
	cin >> q;
	rep(i, q) {
		ll l, r;
		cin >> l >> r;
		auto div = (r - l) / d;
		ll key = l % d;
		if (key == 0) key += d;
		ll v = memo[key][(r - key) / d] - memo[key][(l - key) / d];
		cout << v << endl;
	}
	return 0;
}


Measured memory_bytes: 14644
//tt89 ;)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
void testcase(int t) { cout<<"Case #"<<t<<": "; }
void online() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif //ONLINE_JUDGE
}
const int mod= 1e9+7;

int main() {
    fastIO;
    int n,k; cin>>n>>k;
  int ans=0;
  vector<int> arr(n);
  for(int i=0;i<n;i++) cin>>arr[i];
  sort(arr.begin(),arr.end());
  for(int i=0;i<k;i++) ans+=arr[i];
  cout<<ans;
    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	for(int i=0;i<n;++i)cin>>a[i]>>b[i]>>c[i];
	int x,y,z;
	int dpa=a[n-1],dpb=b[n-1],dpc=c[n-1];
	for(int i=n-2;i>=0;--i)
	{
		x=a[i]+max(dpb,dpc);
		y=b[i]+max(dpa,dpc);
		z=c[i]+max(dpa,dpb);
		dpa=x,dpb=y,dpc=z;
	}
	cout<<max(dpa,max(dpb,dpc));
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N; cin >> N;

	vl num(3,0);

	vl A(N); rep(i,N) cin >> A[i];
	ll ans = 1;
	rep(i,N) {
		ll cnt = 0;
		int index = -1;
		rep(id,3) {
			if(num[id] == A[i]) { cnt++; index = id; }
		}
		if(index == -1) {
			cout << 0 << endl;
			return 0;
		}
		ans *= cnt;
		ans %= mod;
		num[index]++;
	}
    cout << ans << endl;


    return 0;
}



Measured memory_bytes: 1152
#include <iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    int count=0,Cnum=0;
    for(int i=1;i <N;i++){ //partition place
        count =0;
        for(int j=0; j < i ;j++){ //counting number of characters in both
            for (int k=0;k <N ;k++){
                if(k<j && S[j]==S[k]) break;
                else if(k>=i){
                if(S[j]==S[k]){
                count ++;
                break;
                }
                }
            }
        }
         if(Cnum < count) Cnum = count;
    }
    cout << Cnum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K, A=1;
  cin >> N; 
  cin >> K;
  for(int i=0; i < N; i++){
    if(A < K){
      A = 2 * A;
    }
    else if(A >= K){
      A = A + K;
    }
  }
  cout << A << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

int timegap(int a, int b)
{
    return abs(a - b);
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    ll sxor[n + 1];
    ll ssum[n + 1];
    sxor[0] = 0;
    ssum[0] = 0;
    rep(i, 1, n + 1)
    {
        sxor[i] = sxor[i - 1] ^ a[i - 1];
        ssum[i] = ssum[i - 1] + a[i - 1];
        cerr << ssum[i] << endl;
    }
    int start = 0;
    int end = 0;
    ll ans = 0;
    while (end <= n)
    {
        if ((sxor[end] ^ sxor[start]) == (ssum[end] - ssum[start]))
        {
            cerr << (sxor[end] ^ sxor[start]) << " " << (ssum[end] - ssum[start]) << endl;
            ans += end - start;
            end++;
        }
        else
        {
            cerr << "else" << endl;
            do
            {
                start++;
            } while ((sxor[end] ^ sxor[start]) != (ssum[end] - ssum[start]));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = 2e9;
const int MAX=1e7;
const int mod=1e9+7;

int main(){
	ios_base::sync_with_stdio(0);
//		cin.tie(0);

	int n,y;
	while(cin>>n>>y){
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				int tmp=y-i*10000-j*5000;
				if(tmp>=0){
					int k=tmp/1000;
					if(k+i+j==n){
						cout<<i<<" "<<j<<" "<<k<<endl;
						return 0;
					}
				}
			}
		}
		cout<<"-1 -1 -1"<<endl;
	}

	return 0;
}


Measured memory_bytes: 256
from collections import deque
k = int(input())


#初めに、1~9まではキューに入れておく
q = deque([i for i in range(1, 10)])
ans = 0
while True:
    v = q.popleft()
    ans += 1
    if ans == k:
        print(v)
        break
    
    #末尾の1桁を求める
    last_digit = v % 10
    #求めた末尾の1桁との差が1になる数字を最後の1桁にする
    #つまり、末尾の1桁に対して-1,+0,+1とする計算を行う
    for i in range(-1, 2):
        new_digit = last_digit + i
        if new_digit < 0 or new_digit > 9:
            continue
        q.append(v * 10 + new_digit)


Measured memory_bytes: 12404
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define MAXINF 1000000005
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define repc(it, x) for(auto it = (x).begin(); it != (x).end(); ++it)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rrepc(it, x) for(auto it = (x).rbegin(); it != (x).rend(); ++it)
#define all(x) (x).begin(), (x).end()
#define P pair<int, int>

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    int minNum; 
    rep(i,n) {
        if(i == 0) {
            ans++;
            minNum = p[i]; 
        } else {
            if(minNum > p[i]) {
                ans++;
                minNum = p[i];
            }
        }
    } 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

int dp[5005][5005];

int main() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = n-1; i >= 0; i--) {
        for (int j = n-1; j >= 0; j--) {
            if (s[i] != s[j]) dp[i][j] == 0;
            else dp[i][j] = dp[i+1][j+1] + 1;
        }
    }
    int ans = 0;
    rep(i,n)rep(j,n) {
        if (i >= j) continue;
        int now = min(dp[i][j], j-i);
        ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 101360
def is_palindrome(s):
    return all(c1 == c2 for c1, c2 in zip(s, reversed(s)))


S = input()
N = len(S)

if all(is_palindrome(s) for s in (S, S[: (N - 1) // 2], S[(N + 3) // 2 - 1 :])):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
dp = [0]*1001
dp[1] = 1
for i in range(2,1001):
    dp[i]=dp[i-1]+0.5

n,k = map(int,input().split())
p = list(map(int,input().split()))
s = 0
for i in range(k):
    s += p[i]
ans = 0
for i in range(n):
    if i>k-1:
        tmp = tmp + dp[p[i]] - dp[p[i-k]]
        if tmp>ans:
            ans = tmp
    else:
        ans+=dp[p[i]]
        tmp = ans
print(ans)

Measured memory_bytes: 25376
#include <cstdio>
#include <cstring>

using namespace std;

char s[200001];

int main() {
    int n, x = 0, i;
    long long ans = 0;
    
    scanf("%s", s);
    
    n = strlen(s);
    
    for (i = 0; i < n; i++) {
        if (s[n - i - 1] == 'W') continue;
        
        ans += i - x;
        x++;
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>

using namespace std;

const long long MOD = 998244353;
const int MAXN = 3005;
vector<long long> dp(MAXN);

int main()
{
    int n, s;
    scanf("%i%i", &n, &s);
    vector<int> arr(n);
    for (auto &x : arr)
        scanf("%i", &x);
    long long ans = 0;
    for (int x = 0; x < n; x++)
    {
        for (int y = s; y >= arr[x] + 1; y--)
        {
            dp[y] += dp[y - arr[x]];
            dp[y] %= MOD;
        }
        dp[arr[x]] += x + 1;
        dp[arr[x]] %= MOD;
        ans += dp[s];
    }
    printf("%lli\n", ans % MOD);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
#define ll long long int


int main() {
  ll n,neg = 0,sum = 0,sma = 1e9;
  cin >> n;
  vector < ll > v(n);
  for ( int i = 0; i < n; i++ ) {
    cin >> v[i];
    if ( v[i] > 0 ) {
      sum += v[i];
    } else {
      neg++;
      sum -= v[i];
    }
    sma = min(abs(v[i]),sma);
  }

  if ( ( neg % 2 ) == 1 ) {
    cout << sum  - 2 * sma << endl;
  } else {
    cout << sum  << endl;  
  }
  return 0;
}



Measured memory_bytes: 1024