akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
inline int read()
{
	int res, ok = 1;
	char ch;
	for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
	if (ch == '-')
	ok = -1;
	res = ch - '0';
	for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
	res = res * 10 + ch - '0';
	return res * ok;
}
int n, T, a[100005], cnt, num;
set <int> s;
set <int> :: iterator it;
int main()
{
	n = read();
	T = read();
	for (int i = 1; i <= n; i++)
	a[i] = read();
	s.insert (a[1]);
	for (int i = 2; i <= n; i++)
	{
		it = s.begin();
		int now = *it;
		if (a[i] - now > num)
		{
			num = a[i] - now;
			cnt = 0;
		}
		if (a[i] - now == num)
		cnt++;
		s.insert (a[i]);
	}
	printf ("%d\n", cnt);
	return 0;
}

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

int main(){

int a;
string str[100];

cin >> a;

for(int i=0;i<a;i++) cin >> str[i] ;

for(int i=0;i<a;i++){
    for(int j=i+1;j<a;j++){
        if(str[i] == str[j]){
            cout << "No";
            return 0;
             }
        }
    }

 for(int i=0;i<a-1;i++){
         if(str[i].back() != str[i+1].front()){ 
             cout << "No";
             return 0 ;
         
         }
 }

cout << "Yes";
return 0 ;
}

Measured memory_bytes: 256
//
// Created by rect0r on 16-02-2020.
//
#include <bits/stdc++.h>
#define ll long long
#define mod1 (pow(10,9)+9)
#define mod2 (pow(10,7)+7)
#define lim pow(10,9)
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "w", stdout);
#endif*/
    ll T;
    //cin >> T;
    T = 1;
    while (T--) {
        int a[101]={0};
        int x;
        for(int i=0;i<3;i++){
            cin>>x;
            a[x]++;
        }
        int c=0;
        for(int i=1;i<=100;i++){
            if(a[i]>=1)
                c++;
        }
        cout<<c;
        cout << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int mx = 2e5;
vector<int>adj[mx + 5];
bool vis[mx + 5];
int cc = 0;
int nod = 0;
void dfs(int u) {
    vis[u] = true;
    nod++;
    for (auto v : adj[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i(0); i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<int>ans;
    int temp = 0;
    for (int i(1); i <= n; ++i) {
        if (!vis[i]) {
            if (adj[i].size() >= 1)
                temp++;
            nod = 0;
            dfs(i);
            cc++;
            ans.emplace_back(nod);
        }
    }
    int mx = 0;
    for (auto& x : ans) {
        mx = max(mx, x);
    }
    cout << mx << endl;


}

Measured memory_bytes: 20900
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()



int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  
  string s, t;
  cin >> s >> t;
  int n = s.size();
  int ans = 0;
  rep(i, 0, n) {
    if(s[i] != t[i]) ans++;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 3884
#include <bits/stdc++.h>
using namespace std; inline void fileio(const char* in, const char* out) { freopen(in, "r", stdin); freopen(out, "w", stdout); } 
#define TD typedef
#define forx(i,n) for(int i = 0; i < (n); ++i)
#define forxr(i,n) for(int i = (n)-1; i >= 0; --i)
TD long long ll; TD long double ld; TD pair<int,int> pii; TD pair<ll,ll> pll; TD vector<int> VI; TD vector<bool> VB; TD vector<ll> VL;
const char nl = '\n'; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; const ld EPS = 1e-9, PI = acos(-1);
#define ff first
#define ss second
#define all(c) c.begin(),c.end()

const int N = 1005;
ll x[N], y[N], z[N];
int n, m;

struct Comb {
  ll x, y, z;
  Comb(ll a, ll b, ll c): x(a), y(b), z(c) { }
  bool operator<(const Comb& o) const {
    return (x+y+z) < (o.x+o.y+o.z);
  }
};

ll solve(int X, int Y, int Z) {
  vector<Comb> c;
  for (int i = 0; i < n; ++i) {
    c.emplace_back(x[i] * X, y[i] * Y, z[i] * Z);
  }
  sort(c.begin(), c.end());
  ll xx = 0, yy = 0, zz = 0;
  for (int i = 0; i < m; ++i) {
    xx += c[i].x;
    yy += c[i].y;
    zz += c[i].z;
  }
  return abs(xx) + abs(yy) + abs(zz);
}

int main() {
  atexit([](){ cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << nl; });
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout << fixed << setprecision(12);
  // Emily <3
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i] >> z[i];
  }
  ll ans = 0;
  for (int i = 0; i < (1 << 3); ++i) {
    int X = i & 1 ? 1 : -1;
    int Y = i & 2 ? 1 : -1;
    int Z = i & 4 ? 1 : -1;
    ans = max(ans, solve(X,Y,Z));
  }
  cout << ans << nl;

  return 0;
}



Measured memory_bytes: 384
#!/usr/bin/env python3
# -*- coding: utf-8-*-
if __name__ == '__main__':
    N = int(input())
    a = []
    for i in range(5):
        a.append(int(input()))
    m = min(a)
    s = N // m + 4
    if N % m != 0:
        s += 1
    print(s)


Measured memory_bytes: 2940
n,m=map(int,input().split())
a=list(map(int,input().split()))
d={}
k=0
r=0
for i in range(m):
    b,c=map(int,input().split())
    if b in d:
        d[b].append(c)
    else:
        d[b]=[c]
    if c in d:
        d[c].append(b)
    else:
        d[c]=[b]
for key,val in d.items():
    p=0
    if len(val)>0:
        for i in range(len(val)):
            if a[key-1]>a[val[i]-1]:
                p+=1
        if p==len(val):
            k+=1

print(k+n-len(d))

Measured memory_bytes: 98876
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
d = [ int(input()) for _ in range(n) ]

print(len(set(d)))

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,sum=0;
    cin>>n;
    vector<ll>v;
    for(ll i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
            sum+=i;
        }
    }
    cout<<sum;
}


Measured memory_bytes: 3632
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] I = Console.ReadLine().Split(' ');
        char[] S = I[0].ToCharArray();
        char[] T = I[1].ToCharArray();

        for (int i = 0; i < N; i++)
        {
            Console.Write(S[i]);
            Console.Write(T[i]);
        }
    }
}


Measured memory_bytes: 11092
/*
    coded by - PATHAKCODES ~~Revamped
    AIT PUNE , INDIA 
     
    "The Key is not will to win ......everybody has that "
    "It is will to prepare that is important"  
     
*/
     
#include <bits/stdc++.h>
 
using namespace std ;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
const ll k = 1e9 +7;


int main ()
{
	IOS
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int n ;
    cin >> n ;
    vector<ll> a(n,0);

    ll sum = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> a[i];
        sum += a[i];
        sum %= k ;
    }
    ll ans = 0 ;
    for(int i = 0 ;i < n ;i++){
        sum -= a[i];
        if (sum < 0) sum += k;
        ans += a[i]*sum ;
        ans%=k;
    }

    cout << ans << endl ;
}

Measured memory_bytes: 4760
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N; cin >>N;
  vector<int>H(N);
  vector<int>saitei(N);
  for(int i=0;i<N;i++){
    cin>>H.at(i);
  }
  saitei.at(0)=0;
  for(int i=1;i<N;i++){
    cin>>H.at(i);
    saitei.at(i)=max(saitei.at(i-1),H.at(i)-1);
  }
  bool hantei=true;
  rep(i,N){
    if(i<N-1){
      if(H.at(i)>H.at(i+1)+1){
        hantei=false;
        break;
      }
    }
    if(H.at(i)<saitei.at(i)){
      hantei=false;
      break;
    }
  }
  if(hantei){
    cout <<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

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

using namespace std;



int main(){
    int n;
    string s;
    cin >> n >> s;
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'B'){
            if(s[i-1] == 'A' && s[i+1] == 'C') res++;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>//必須

int compare_int(const void *a, const void *b)//事前に入れる
{
    return *(int*)a - *(int*)b;
}


int main(void){
    // Your code here!
    int N,K;
    
    scanf("%d %d",&N,&K);
if(K==1){printf("0\n");
    
}else{
   printf("%d",N-K);}
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)


typedef long long ll;
typedef pair<ll, ll> P;


int dist[1100000];
pair<int, int> pos[1100000];

int main()
{
  int H, W, D;
  cin >> H >> W >> D;
  REP(i, H) {
    REP(j, W) {
      int A;
      cin >> A;
      pos[A].FI = i;
      pos[A].SE = j;
    }
  }

  REP(i, H*W) {
    dist[i + D] = dist[i] + abs(pos[i+D].FI - pos[i].FI) + abs(pos[i+D].SE - pos[i].SE);
  }

  int Q;
  cin >> Q;
  REP(i, Q) {
    int L, R;
    cin >> L >> R;
    cout << dist[R] - dist[L] << endl;
  }

  return 0;
}

Measured memory_bytes: 3840
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int res=n%10;
    if(res==2 || res==4 || res==5 || res==7 || res==9)
      cout<<"hon";
    else if(res==0 || res== 1 || res== 6 || res== 8)
      cout<<"pon";
    else
       cout<<"bon";
    

    return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll=long long;

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	
	if(a+b+c>=22)cout<<"bust"<<endl;
	else cout<<"win"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

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

int get_rand(int a, int b) {  // [a, b]
    return uniform_int_distribution<int>(a, b)(rng);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int d = 365, n = 26;
    vector<int> c(n);
    vector<vector<int>> s(d, vector<int>(n));
    if (true) {
        cin >> d;
        for (int i = 0; i < n; i++) {
            cin >> c[i];
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < n; j++) {
                cin >> s[i][j];
            }
        }
    } else {
        for (int i = 0; i < n; i++) {
            c[i] = get_rand(0, 100);
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < n; j++) {
                s[i][j] = get_rand(0, 20000);
            }
        }
    }
    auto beg = clock();
    int cnt = 0;
    int wid = 12;
    int lrand = 20;
    vector<vector<int>> que(wid, vector<int>(d));
    for (int i = 0; i < wid; i++) {
        for (int j = 0; j < d; j++) {
            que[i][j] = get_rand(0, n - 1);
        }
    }
    auto get = [&](int id) {
        int res = 0;
        vector<int> last(n, -1);
        for (int i = 0; i < d; i++) {
            res += s[i][que[id][i]];
            int x = i - last[que[id][i]] - 1;
            res -= c[que[id][i]] * x * (x + 1) / 2;
            last[que[id][i]] = i;
        }
        for (int i = 0; i < n; i++) {
            int x = d - last[i] - 1;
            res -= c[i] * x * (x + 1) / 2;
        }
        return res;
    };
    while (true) {
        cnt++;
        if (clock() - beg > 1919191) {
            break;
        }
        vector<pair<int, vector<int>>> nxt(wid + 1);
        for (int i = 0; i < wid; i++) {
            nxt[i].first = -1e9;
        }
        for (int i = 0; i < wid; i++) {
            for (int j = 0; j < lrand; j++) {
                int p = get_rand(0, n - 1);
                int q = get_rand(0, d - 1);
                swap(p, que[i][q]);
                nxt[wid] = make_pair(get(i), que[i]);
                for (int k = wid - 1; k >= 0; k--) {
                    if (nxt[k].first < nxt[k + 1].first) {
                        swap(nxt[k], nxt[k + 1]);
                    } else {
                        break;
                    }
                }
                swap(p, que[i][q]);
            }
        }
        for (int i = 0; i < wid; i++) {
            que[i] = nxt[i].second;
        }
    }
    for (int i = 0; i < d; i++) {
        cout << que[0][i] + 1 << '\n';
    }
    cerr << get(0) << '\n';
    cerr << cnt << '\n';
    return 0;
}


Measured memory_bytes: 3780
A, B, C, D = map(int, input().split())


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


E = C * D // gcd(C, D)
total = 0

total += B // C - (A-1) // C


total += B // D - (A-1) // D


total = total - B // E + (A-1) // E

print(B - A + 1 - total)

Measured memory_bytes: 3064
#include <iostream>
#include<bits/stdc++.h>
#include<vector>
#include<string>
#define ll long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vi vector<ll>
#define el printf("\n")
#define N 100001
using namespace std;



int main()
{   IOS;
cout.precision(30);
    ll n;
    cin >> n;
    vector<ll> L(n,0);
    bool B=true;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin >> x;
        L[i]=x;

    }
    ll res=0;
    for(int i=1;i<n-1;i++)
    {
        if((L[i]>=L[i-1] && L[i]<=L[i+1] ) ||(L[i]<=L[i-1] && L[i]>=L[i+1])  )
            res++;
    }
    cout << res;


    return 0;
}


Measured memory_bytes: 256
from collections import Counter

N = int(input())
V = tuple(map(int, input().split()))
X, Y = Counter(), Counter()
for i in range(0, N):
    if i & 1:
        Y[V[i]] += 1
    else:
        X[V[i]] += 1
if len(X) != 1:
    x = sorted(X.items(), reverse=True, key=lambda x: x[1])[:2]
else:
    x = sorted(X.items(), reverse=True, key=lambda x: x[1])[:1]
if len(Y) != 1:
    y = sorted(Y.items(), reverse=True, key=lambda x: x[1])[:2]
else:
    y = sorted(Y.items(), reverse=True, key=lambda x: x[1])[:1]
if x[0][0] == y[0][0]:
    ans = N
    tmp = 0
    if len(y) == 1:
        for i in range(0, N):
            if i & 1:
                if V[i] != y[0][0]+1:
                    tmp += 1
            else:
                if V[i] != x[0][0]:
                    tmp += 1
    else:
        for i in range(0, N):
            if i & 1:
                if V[i] != y[1][0]:
                    tmp += 1
            else:
                if V[i] != x[0][0]:
                    tmp += 1
    ans = min(ans, tmp)
    tmp = 0
    if len(x) == 1:
        for i in range(0, N):
            if i & 1:
                if V[i] != y[0][0]:
                    tmp += 1
            else:
                if V[i] != x[0][0]+1:
                    tmp += 1
    else:
        for i in range(0, N):
            if i & 1:
                if V[i] != y[0][0]:
                    tmp += 1
            else:
                if V[i] != x[1][0]:
                    tmp += 1
    ans = min(ans, tmp)
else:
    ans = 0
    for i in range(0, N):
        if i & 1:
            if V[i] != y[0][0]:
                ans += 1
        else:
            if V[i] != x[0][0]:
                ans += 1
print(ans)


Measured memory_bytes: 17560
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

max_c = 0
index_c = 0

for i, C in enumerate(c):
    if C > max_c:
        index_c = i
        max_c = C

for d in range(D):
    print(index_c+1)


Measured memory_bytes: 9508
N,K=gets.split.map &:to_i
W=$<.map &:to_i
l=0
r=$$**3
m=r/2
def a m
i=k=s=0
while i<N
return if m<w=W[i]
s+=w
i+=1
m<s&&(s=w)&k+=1
end
k<K
end
while l+1<r
a(m)?r=m :l=m
m=(l+r)/2
end
p r

Measured memory_bytes: 7032
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;
const long long MOD = 1000000007;

typedef long long ll;
const ll INF = 1LL << 50;
vector<int> v[200000];
ll cnt[200000];

void dfs(int i) {
  for (int j = 0; j < v[i].size(); j++) {
    cnt[v[i][j]] += cnt[i];
    dfs(v[i][j]);
  }
  return;
}

int
main(void) {
  int n, q;
  scanf("%d %d", &n, &q);
  int a, b;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d %d", &a, &b);
    a--; b--;
    v[a].push_back(b);
  }

  int p; ll x;
  for (int i = 0; i < q; i++) {
    scanf("%d %lld", &p, &x);
    p--;
    cnt[p] += x;
  }

  dfs(0);

  for (int i = 0; i < n; i++) printf("%lld ", cnt[i]);

  return 0;
}
  


Measured memory_bytes: 24320
#include <bits/stdc++.h>
using namespace std;
#define INF 2000000000
typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1LL<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1LL<<(i))))
#define setbit1(n,i) ((n)|(1LL<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define DBG(a) cout<<#a<<" ->->->-> "<<a<<endl
#define EN cout<<"\n"
#define fi first
#define se second
#define PI (acos(-1))
#define fastread ios::sync_with_stdio(false);cin.tie(NULL)
#define mod (1000000007)
#define asz 1000005
template<class T> ostream& operator<<(ostream &s,pair<T,ll> a)
{
    s<<a.fi<<' '<<a.se;
    return s;
}
int main()
{
    fastread;
    ll T=1;
//    cin>>T;
    for(ll qq=1;qq<=T;qq++)
    {
        ll n,k;
        cin>>n>>k;
        k+=100*max(0LL,10-n);
        cout<<k<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
N, M = gets.chomp.split(' ').map(&:to_i)
ks = []
M.times do
  t = gets.chomp.split(' ').map(&:to_i)
  ks << [t.shift, t]
end
P = gets.chomp.split(' ').map(&:to_i)
result = 0
(0..2**N-1).map{|n|n.to_s(2).rjust(N, '0')}.each do |c|
  light = false
  M.times do |i|
    xor = 0
    ks[i][0].times do |j|
      xor ^= c[ks[i][1][j] - 1].to_i
    end
    if xor != P[i]
      light = true
      break
    end
  end
  if !light
    result += 1
  end
end
puts result

Measured memory_bytes: 4092
# https://drken1215.hatenablog.com/entry/2020/04/20/003900
# k  個足してできる最小の整数を求める (a とする)
# k 個足してできる最大の整数を求める (b とする)
# 出来上がる整数は b−a+1 個である

N, K = map(int, input().split())
mod = 10 ** 9 + 7

ans = 0
for k in range(K, N+2):
    mx = k * (2 * N - k + 1) / 2
    mi = k * (k - 1) / 2
    add = mx - mi + 1
    ans += add
    ans %= mod
print(int(ans))

Measured memory_bytes: 9116
N = int(input())
s = ''
i = 0
while N != 0:
    tmp = N % 2
    s += str(tmp)
    N = N - tmp * (-1)**i
    N = (N//2)
    i += 1
s = s[::-1]
if s == '':
    print(0)
else:
    print(s)

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;

int main()
{
    double r;
    
    cin >> r;
    
    double area = r * r * M_PI;
    double length = 2 * M_PI * r;
    
    printf("%.8lf %.8lf\n", area, length);
    
    return 0;
}


Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const long long INF = 2000000000;
using namespace std;

const long long MAX_N = 4005;
long long g[MAX_N][MAX_N] = {0};
long long imos[MAX_N][MAX_N] = {0};

void compress(vector<long long> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}

long long lb(vector<long long> v, long long num){
    return lower_bound(all(v), num) - v.begin();
}

int main(){
    long long n;
    cin >> n;

    pair<pair<long long, long long>, pair<long long, long long>> inp[MAX_N];
    vector<long long> x, y;
    rep(i,n){
        cin >> inp[i].first.first >> inp[i].first.second >> inp[i].second.first >> inp[i].second.second;
        x.emplace_back(inp[i].first.first);
        x.emplace_back(inp[i].second.first);
        y.emplace_back(inp[i].first.second);
        y.emplace_back(inp[i].second.second);
    }
    compress(x);
    compress(y);

    rep(i,n){
        long long lx = lb(x, inp[i].first.first);
        long long ly = lb(y, inp[i].first.second);
        long long rx = lb(x, inp[i].second.first);
        long long ry = lb(y, inp[i].second.second);

        for(long long j = ly; j < ry; j++) g[j][lx]++;
        for(long long j = ly; j < ry; j++) g[j][rx]--;
    }

    rep(i,y.size()){
        long long c = 0;
        rep(j,x.size()){
            c+=g[i][j];
            imos[i][j] = c;
        }
    }

    //rep(i,5){ rep(j,5){ cout << imos[i][j] << ' '; } cout << endl; }

    long long sum = 0;
    range(i,0,y.size()){
        range(j,0,x.size()){
            if(imos[i][j] != 0){
            //if(imos[i][j] != 0 && imos[i][j + 1] != 0 && imos[i + 1][j] != 0 && imos[i + 1][j + 1] != 0){
                //cout << (y[i + 1] - y[i]) << ' ' <<   (x[j + 1] - x[j])  << endl;;
                //sum += (y[i + 1] - y[i]) * (x[j + 1] - x[j]);
                sum += abs(y[i + 1] - y[i]) * abs(x[j + 1] - x[j]);
            }
        }
    }
    cout << sum << endl;

}

Measured memory_bytes: 253468
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h> //円周率はM_PI
using namespace std;


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

	vector<int64_t> L(N+1);
	L.at(0) = 2;
	L.at(1) = 1;

	for (int i = 2; i < N+1; i++) {
		L.at(i) = L.at(i - 1) + L.at(i - 2);
	}

	cout << L.at(N) << endl;

}


Measured memory_bytes: 256
num = input()
d = []
num = int(num)
for n in range(num):
    t, s = input().split()
    d.append([t,s])
flag = 0
for n in range(num):
    if(n<num-2):
        if(d[n][0]==d[n][1] and d[n+1][0]==d[n+1][1] and d[n+2][0]==d[n+2][1]):
            flag = 1
if flag == 1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9200
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
   int n;
  scanf("%d",&n);
  int i,max=0;
  int cnt=0;
  char ch;
  for(i=1;i<=n;++i)
  {
     cin>>ch;
     if(ch=='I')
     { cnt+=1;
        if(max<cnt)
            max=cnt;
     }
    
     else
     {
       cnt-=1;
        if(max<cnt)
            max=cnt;
     }
  }
  
  printf("%d",max);
}

Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))
iCnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[i] == L[j] or L[i] == L[k] or L[j] == L[k]:
                continue
            if L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
                iCnt += 1
print(iCnt)

Measured memory_bytes: 9148
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) //[l, r)
#define rep(i,n) REP(i,0,n)           //[0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showslr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i];}cerr<<endl //[l, r))

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

inline void io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}

void _DEBUG(){cerr<<endl;}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<",";_DEBUG(b...);}

template<typename T> inline void in(T &e){cin>>e;}
template<typename H,typename... T>void in(H &a, T&... b){in(a);in(b...);}
template<typename T> inline void out(T e){cout<<e<<endl;}
template<typename H,typename... T> void out(H a, T... b){out(a);out(b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int n;
string s,t;

signed main(){
    io();
    in(n,s,t);
    bool f;
    int l=0;
    rep(i,n){
        f=true;
        rep(j,n){
            if(j+i>=n) break;
            //show(j+i,j);
            if(s[j+i]!=t[j]){
                f=false;
                break;
            }
        }
        if(f) l=max(l,n-i);
    }
    out(2*n-l);

    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int a, b, c, ans = 0;
    cin >> a >> b >> c;
    int m = max({a, b, c}), sum = a + b + c;
    int t = 3 * m - sum;
    ans = (t + 1) / 2 + (t % 2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# まずは自力で。
# 次に累積和。

n, q = map(int, input().split())
S = input()

L = []
R = []

for i in range(q):
    a,b = map(int, input().split())
    L.append(a)
    R.append(b)


ans = [0]

for i in range(n-1):
    if S[i:i+2] == 'AC':
        ans.append(ans[i]+1)
    else:
        ans.append(ans[i])

        
for i in range(q):
    print(ans[R[i]-1]-ans[L[i]-1])


Measured memory_bytes: 14228
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  int K;
  cin >> K;
  if(K%7==0){
    K/=7;
  }
  K*=9;
  ll test=1;
  for(int i=1;i<=K;i++){
    test=test*10%K;
    if(test==(1%K)){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int inf = 1000000000; 

int main(){
int r;
cin >> r;
cout << fixed << setprecision(10) << 2*M_PI*r << endl;
}

Measured memory_bytes: 3788
#include <iostream>
using namespace std;
int main()
{
	int n,ans = 0,max = 0,s;
	cin >> n;
	while(n --)
	{
		cin >> s;
		max = max > s ? max : s;
		ans += s;
	}
	if(ans > 2 * max)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
// const int mod = 1000000007;
using namespace std;
// const int N = 1e5 + 5; 
// int n;
// int a[N];

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
int a,b;
cin >> a >> b;
cout << a*b << endl;
return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int N=1e5+10;
const int p=1e9+7;
int n,m,k,a[N],l[N],dp[110][N];
map<int,int> b;
int main(){
	cin>>n>>k;
	for(int x=1,gx;x<=n;x=gx+1){
		gx=n/x?min(n/(n/x),n):n;
		a[++m]=gx;l[m]=gx-x+1;
		b[gx]=m;
	}
//	for(int i=0;i<=m;i++){
//		cout<<b[i]<<" ";
//	}
//	cout<<endl;
	for(int j=0;j<=m;j++)dp[0][j]=1;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=(dp[i][j-1]+(long long)l[j]*dp[i-1][b[n/a[j]]]%p)%p;
//			cout<<dp[i][j]<<" ";
		}
//		cout<<endl;
	}
	cout<<dp[k][m]<<endl;
	
	return 0;
} 

Measured memory_bytes: 44152
#include <stdio.h>

int main(void)
{
	double w;
	
	while(scanf("%lf", &w) != EOF){
		
		if(w <= 48.00){
			printf("light fly\n");
		}
		else if(w <= 51.00){
			printf("fly\n");
		}
		else if(w <= 54.00){
			printf("bantam\n");
		}
		else if(w <= 57.00){
			printf("feather\n");
		}
		else if(w <= 60.00){
			printf("light\n");
		}
		else if(w <= 64.00){
			printf("light welter\n");
		}
		else if(w <= 69.00){
			printf("welter\n");
		}
		else if(w <= 75.00){
			printf("light middle\n");
		}
		else if(w <= 81.00){
			printf("middle\n");
		}
		else if(w <= 91.00){
			printf("light heavy\n");
		}
		else{
			printf("heavy\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 608
#include <iostream>
#include <vector>
#include <algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
using namespace std;

const int MOD=1e9+7;
const int N=1e5+7;

std::vector<int> v[N];
int check[N];
int val[N];
int xx;


int dfs(int x)
{
	if( check[x] == 1 )
		return val[x];
	check[x] = 1; 
	val[x] = 1;
	for (int a: v[x])
	{
		val[x] = max(val[x], 1 + dfs(a));
	}
	return val[x];
}


int main()
{
	IOS;
	int n, m, x, y;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> x >> y;
		v[x].push_back(y);
	}
	for (int i = 1; i <= n ; ++i)
	{
		xx = max(xx, dfs(i));
	}
	cout << (xx-1) <<"\n";
	return 0;
}



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

int main(){
	int n;
	cin >> n;
	map<pair<string, int>, int> A;
	string s;
	int num;

	for(int i=0; i<n; ++i){
		cin >> s >> num;
		//A.insert(make_pair(make_pair(s, 100-num),i+1));
		A.insert({{s, -num},i+1});
	}
	//sort(A.begin(),A.end());
	for(auto it=A.begin(); it!=A.end(); it++){
		cout << (*it).second << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
#include<vector>
#define fo(i,n) for(long long i=0;i<n;i++)
#define ll long long int
#define inf 999999999999999999
#define pb push_back
#define fi first
#define se second
#define vi vector<ll>
#define vii vector<vector<ll>>
#define pi pair<ll,ll>
#define mp make_pair
#define MOD 1000000007
#define tr(c,it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define fio ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
//cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
//freopen("explicit.in", "r", stdin);
//freopen("explicit.out", "w", stdout);
 
void SieveOfEratosthenes() 
{ 
    bool prime[10000001];
    memset(prime, true, sizeof(prime)); 
  
    for (ll p=2; p*p<=10000000; p++) 
    { 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (ll i=p*p; i<=10000000; i += p) {
                prime[i] = false; 
            }
        } 
    }  
} 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a);
        a = (a * a);
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
	if(b%a==0)
	   return a;
	return gcd(b%a,a);
}
ll power(ll x,ll y,ll p) 
{ 
    ll r = 1;
  
    x = x % p;
    while (y > 0) {
        if (y & 1) 
            r = (r * x) % p;
        y = y >> 1; 
        x = (x * x) % p; 
    } 
    return r; 
}  
ll modInverse(ll n, ll p) 
{ 
    return power(n, p - 2, p); 
} 
 
ll nCrModP(ll n,ll r, ll p) 
{ 
    ll fac[100005];
    if (r == 0) 
        return 1; 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
}
int32_t main() 
{
    fio
	ll j,i,n,t,l,r,c,h,k,m,maxi,d,x;
	cin>>x;
	if(x)
		cout<<0;
	else
		cout<<1;
}




	

		

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<map>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<list>
#include<string>
#include<climits>
#define ll long long 
#define inf 0x7f7f7f7f
#define io ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct q
{
	int l,r;
}p[100005];
bool cmp(q a,q b)
{
	if(a.l==b.l)
	return a.r<b.r;
	return a.l<b.l;
}
int main()
{
	int n;
	cin>>n;
	int x,k;
	for(int i=0;i<n;i++)
	{
		cin>>x>>k;
		p[i].l=x-k;
		p[i].r=x+k;
	}
	sort(p,p+n,cmp);
	int ans=n;
	int rr=p[0].r;
	for(int i=1;i<n;i++)
	{
		if(p[i].l<rr)
		{
			ans--;
			rr=min(rr,p[i].r);
		}
		else
		{
			rr=p[i].r;
		}
	}
	cout<<ans;
} 

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>
#include <cstdio>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;
using P = pair<int,int>;
using TP = tuple<int,int,int>;

int main() {
    int h,w,ch,cw,dh,dw;
    scanf("%d %d %d %d %d %d",&h, &w,&ch,&cw,&dh,&dw);

    char s[h+1][w+1];
    for (int i=0; i<h; i++) {
        scanf("%s",s[i]);
    }

    vector num(h, vector(w,-1));

    const vector dx = {-1,0,+1,0};
    const vector dy = {0,+1,0,-1};

    priority_queue<TP, vector<TP>, greater<>> q;
    q.emplace(0, ch-1,cw-1);
    while(!q.empty()) {
        const auto [c,y,x] = q.top(); q.pop();
        if (x<0 || w<=x) continue;
        if (y<0 || h<=y) continue;
        if (s[y][x] == '#') continue;
        if (num[y][x]>=0 && num[y][x]<=c) continue;
        num[y][x] = c;
        if (y+1 == dh && x+1 == dw) break;


        for (short i=0; i<4; i++) {
            const int xi = x + dx[i];
            const int yi = y + dy[i];
            if (xi<0 || w<=xi) continue;
            if (yi<0 || h<=yi) continue;
            if (s[yi][xi] == '#') continue;
            q.emplace(c,yi,xi);
        }

        for (short i=-2; i <=2; i++) {
            const int yi = y + i;
            if (yi<0 || h<=yi) continue;
            for (short j=-2; j<=2; j++) {
                const int xi = x + j;
                if (xi<0 || w<=xi) continue;
                if (s[yi][xi] == '#') continue;
                if (num[yi][xi]>=0 && num[yi][xi]<=c) continue;
                q.emplace(c+1,yi, xi);
            }
        }
    }


    cout << num[dh-1][dw-1] << endl;
}


Measured memory_bytes: 9444
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
using namespace std;

template<class T>
void in(vector<T>& V) {
	for (auto itr = V.begin(); itr != V.end(); itr++)cin >> *itr;
	return;
}

template<class T>
void out(vector<T>& V) {
	for (T& itr : V)cout << itr << endl;
	return;
}

long long N, K;
vector<long long> A, B;

int main() {
	cin >> N >> K;
	A.resize(N);
	B.resize(N);
	for (int n = 0; n < N; n++)cin >> A[n] >> B[n];
	long long ans = 0;
	for (int c = 29; c >= 0; c--) {
		if ((K >> c)&1) {
			long long KK = K;
			KK >>= (c + 1);
			KK <<= (c + 1);
			long long temp = 0;
			for (int n = 0; n < N; n++) {
				long long AA = A[n];
				AA >>= (c);
				AA <<= (c);
				if (((~KK)&AA) == 0) {
					temp += B[n];
				}
			}
			ans = max(ans, temp);
		}
	}
	long long temp = 0;
	for (int n = 0; n < N; n++) {
		if ((A[n] | K) == K)temp += B[n];
	}
	ans = max(ans, temp);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
def main():
    N, K = list(map(int, input().split(' ')))
    x = list(map(int, input().split(' ')))  # already sorted
    left = - min([x[0], 0])
    right = max([x[K - 1], 0])
    min_t = min([2 * left + right, left + 2 * right])
    for i in range(N):
        if i + K - 1 > N - 1:
            break
        left = - min([x[i], 0])
        right = max([x[i + K - 1], 0])
        min_t = min([min_t, min([2 * left + right, left + 2 * right])])
    print(min_t)


if __name__ == '__main__':
    main()

Measured memory_bytes: 14096
# include<bits/stdc++.h>
using namespace std;
int main (){
string s;
cin>>s;
if(s[0]==s[1] and s[1]==s[2]){
    cout<<"Yes";
}
else if (s[1]==s[2] and s[2]==s[3]){
    cout<<"Yes";
}
else
    cout<<"No";
}


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

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 10;

int main(){
	ios_base::sync_with_stdio (false);
	int n, k;
	string s;
	cin >> n >> k >> s;
	for (int i = 0; i < n; i++){
		if (i != k - 1){
			cout << s[i];
			continue;
		}
		if (s[i] == 'A')
			cout << 'a';
		else if (s[i] == 'B')
			cout << 'b';
		else
			cout << 'c';
	}
	cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
 
#define ff                  first
#define ss                  second
#define endl                "\n"
#define loop(i,s,e)         for(int i=s;i<e;i++)
#define int                 long long
#define vi                  vector<int> 
#define S(v)                sort(v.begin(),v.end())
#define RS(v)               sort(v.rbegin(),v.rend())
#define R(v)                reverse(v.begin(),v.end())
#define mxpq(T)             priority_queue <T>
#define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
#define prv(v)              for(auto &x : v)cout << x << " ";
#define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
#define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
#define mp                  make_pair
#define pii                 pair<int,int>
#define mset(a,f)           memset(a , f , sizeof(a))
#define pb                  push_back
#define inf                 INT_MAX
#define INF                 LLONG_MAX
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
 
const int N = 2e6 + 6;
const int M = 1e9+7;
int A[N];
int n , m;
inline int mul(int a, int b) { return (a * b) % M; };
inline int add(int a, int b)
{
      int res = a + b;
      if ( res < 0 ) res += M;
      if ( res >= M) res -= M;
      return res;
}

void solve()
{
	int n;
	cin >> n;
	int a = (n-1) , b = n;
	int a1 = 1 , a2 = 1 , a3 = 2;
	int ans = 0;
	loop(i,0,n)
	{
		a1 = ((a1%M)*(10%M))%M;
	}
	loop(i,0,n)
	{
		a2 = ((a2%M)*(8%M))%M;
	}
	loop(i,0,n)
	{
		a3 = ((a3%M)*(9%M))%M;
	}
	a3 %=M;
	ans = add(a1%M , a2%M);
	ans = add(ans%M , -a3);
	// ans = ((ans%M)*(b%M))%M;
	// ans = ((ans%M)*(a%M))%M;


	cout << ans%M;
}			
 
int32_t main()
{
 
cout<<fixed<<setprecision(16);
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
 	
 
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}

Measured memory_bytes: 3608
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

P = 10**9 + 7

S = input()
N = len(S)

psumA = [0] + list(accumulate(c == 'A' for c in S))
psumC = [0] + list(accumulate(c == 'C' for c in S))
psumX = [0] + list(accumulate(c == '?' for c in S))
Q = psumX[N]

ans = 0
for i in range(1, N-1):
  if S[i] == 'B':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q, P) % P
    if Q >= 1:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
  if S[i] == '?':
    ans += psumA[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-1, P) % P
    if Q >= 2:
      ans += psumX[i] * (psumC[N] - psumC[i+1]) % P * pow(3, Q-2, P) % P
      ans += psumA[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-2, P) % P
    if Q >= 3:
      ans += psumX[i] * (psumX[N] - psumX[i+1]) % P * pow(3, Q-3, P) % P

print(ans % P)



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

constexpr int INF = 1e9;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> v(H, vector<int>(W));
    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            cin >> v[i][j];
        }
    }
    vector<vector<int>> sum(H, vector<int>(W+1));
    for(int i=0; i<H; ++i) {
        for(int j=W-1; j>=0; --j) {
            if(v[i][j] == 0) {
                sum[i][j] = sum[i][j+1] + 1;
            }
        }
    }
    int res = 0;
    for(int i=0; i<W; ++i) {
        stack<int> lst, rst;
        vector<int> L(H), R(H);
        for(int j=0; j<H; ++j) {
            while(!lst.empty() && sum[lst.top()][i] >= sum[j][i]) {
                lst.pop();
            }
            while(!rst.empty() && sum[rst.top()][i] >= sum[H-1-j][i]) {
                rst.pop();
            }
            if(sum[j][i] == 0) {
                L[j] = j;
            } else {
                L[j] = (lst.empty() ? 0 : lst.top() + 1);
            }
            if(sum[H-1-j][i] == 0) {
                R[H-1-j] = H-1-j;
            } else {
                R[H-1-j] = (rst.empty() ? H : rst.top());
            }
            lst.push(j);
            rst.push(H-1-j);
        }
        for(int j=0; j<H; ++j) {
            res = max(res, sum[j][i] * (R[j] - L[j]));
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 18008
#include<iostream>
#include<vector>
#define LEN 100005

using namespace std;

vector<int> mark[LEN];
int lk[LEN]={0};
bool status[LEN]={0};
int fleed = 1;
int n;
/*
void find(int a){
//	if()return false;
	if(a==b)return true;
	status[a]=true;
	int len = mark[a].size();
	for(int i =0;i<len;++i){
		if(!status[mark[a][i]]){
		lk[mark[a][i]] = fleed;	
		if(find(mark[a][i],b))return true;
		}
	}

	return false;
	
}
*/

void dfs(int i){
	status[i] = true;
	lk[i] = fleed;
	for(int k = 0;k<mark[i].size();++k){
		if(!status[mark[i][k]])dfs(mark[i][k]);
	} 
}
void dfs(){
	for(int p = 0;p<n;++p){
		if(!status[p]){
			dfs(p);
			++fleed;
		}
	}
}
inline void insert(int a,int b){
	mark[a].push_back(b);
	mark[b].push_back(a);
}

int main(){
	int m,s,tmpa,tmpb;
	cin>>n>>m;
	while(m--){
		cin>>tmpa>>tmpb;
		insert(tmpa,tmpb);
	}
	dfs();
	cin>>s;
	while(s--){
	cin>>tmpa>>tmpb;
	if(lk[tmpa]&&lk[tmpa]==lk[tmpb])cout<<"yes"<<endl;
	else cout<<"no"<<endl;
	}
	return 0;
}


Measured memory_bytes: 12164
s = input()
flag = [0] * 4
for i in range(len(s)):
    if s[i] == "N":
        flag[0] = 1
    elif s[i] == "W":
        flag[1] = 1
    elif s[i] == "S":
        flag[2] = 1
    else:
        flag[3] = 1

print("Yes" if flag[0] == flag[2] and flag[1] == flag[3] else "No")

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

int main() {
  string s,t;
  cin>>s;
  t="YAKI";
  int b=0;
  if(s.size()>=4)for(int i=0;i<4;i++)if(s[i]==t[i])b++;
  if(b==4)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int n,m;
    cin >> n>>m;

    int a[105][105];
    int b[105];

    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < m;i++){
        cin >> b[i];
    }

    for (int i = 0; i < n;i++){
        int c = 0;
        for (int j = 0; j < m;j++){
            c += a[i][j] * b[j];
        }
        cout << c << endl;
    }
}


Measured memory_bytes: 3152
#include <iostream>
#include <string>
#include <map>

using namespace std;

const string North = "North";
const string South = "South";
const string East = "East";
const string West = "West";
const string Right = "Right";
const string Left = "Left";

int main(void){
    // Your code here!
    while(true){
        int N;
        cin >> N;
        if(N == 0){
            break;
        }
        int northNum = 5;
        int southNum = 2;
        int eastNum = 3;
        int westNum = 4;
        int top = 1;
        int ans = 0;
        for(int i=0;i<N;i++){
            string ope;
            cin >> ope;
            if(ope == North){
                int temp = top;
                top = southNum;
                southNum = 7 - temp;
                northNum = temp;
            }else if(ope == South){
                int temp = top;
                top = northNum;
                northNum = 7 - temp;
                southNum = temp;
            }else if(ope == East){
                int temp = top;
                top = westNum;
                westNum = 7 - temp;
                eastNum = temp;
            }else if(ope == West){
                int temp = top;
                top = eastNum;
                eastNum = 7 - temp;
                westNum = temp;
            }else if(ope == Right){
                int temp = northNum;
                northNum = westNum;
                westNum = southNum;
                southNum = eastNum;
                eastNum = temp;
            }else if(ope == Left){
                int temp = northNum;
                northNum = eastNum;
                eastNum = southNum;
                southNum = westNum;
                westNum = temp;
            }
            ans += top;
        }
        
        cout<< ans + 1 <<endl;
    }
    return 0;
}



Measured memory_bytes: 3132
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int x; cin >> x;
	x /= 100;
	string s = "ai1333";
	rep(i, 0, x)s += "3";
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3236
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]", B: "List[int]"):
    sum=0
    temp=0
    for i in range(N):
        if B[i]<=(A[i]-temp):
            sum+=B[i]+temp
            temp=0
        else:
            if(temp>=A[i]):
                temp=B[i]
            else:
                temp=B[i]-A[i]+temp
            sum+=A[i]
    
    if(A[N]>=temp):sum+=temp
    else: sum+=A[N]
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N + 1)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 21576