akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
R, S, P = map(int,input().split())
T = input()
ans = 0
jr = [0]*N
js = [0]*N
jp = [0]*N
if T[0] == 'r':
  ans += P
  jr[0] = 1
elif T[0] =='s':
  ans += R
  js[0] = 1
else:
  ans += S
  jp[0] = 1
for i in range(1,N):
  if i < K:
    if T[i] == 'r':
      jr[i] = 1
      ans += P
    elif T[i] == 's':
      js[i] = 1
      ans += R
    else:
      jp[i] = 1
      ans += S
      
  elif i + K < N:
    if T[i] == 'r':
      if jr[i-K] == 0:
        jr[i] = 1
        ans += P
        
    elif T[i] == 's':
      if js[i-K] == 0:
        js[i] = 1
        ans += R
    
    elif T[i] == 'p':
      if jp[i-K] == 0:
        jp[i] = 1
        ans += S
  else:
    if T[i] == 'r':
      if jr[i-K] == 0:
        jr[i] = 1
        ans += P
        
    elif T[i] == 's':
      if js[i-K] == 0:
        js[i] = 1
        ans += R
        
    elif T[i] == 'p':
      if jp[i-K] == 0:
        jp[i] = 1
        ans += S
        
        
print(ans)

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

int main() {

	int k;
	string s;

	cin >> k;
	cin >> s;

	int len = s.size();

	if (len <= k) {
		cout << s << endl;
	}

	if (len > k) {
		cout << s.erase(k) << "..." << endl;
	}

	return 0;
}

Measured memory_bytes: 3592
import sys
readline=sys.stdin.buffer.readline

N=int(readline())

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors

div=make_divisors(N)
#print(div)

answer=0
for i in range(len(div)):
  d=div[i]-1
  if d!=0 and N//d==N%d:
    answer+=d
print(answer)

Measured memory_bytes: 39024
N, C = map(int, input().split())
D = []
for i in range(0, C):
	D.append(list(map(int, input().split())))
colors = [[], [], []]
for i in range(0, N):
	A = list(map(lambda v: int(v)-1, input().split()))
	for j in range(0, N):
		colors[(i+j)%3].append(A[j])
sums = [[], [], []]
for i in range(0, 3):
	for j in range(0, C):
		sum = 0
		for k in range(0, len(colors[i])):
			sum += D[colors[i][k]][j]
		sums[i].append(sum)
min = 5000000000000000
for i in range(0, C):
	for j in range(0, C):
		if i != j:
			for k in range(0, C):
				if i != k and j != k:
					if sums[0][i] + sums[1][j] + sums[2][k] < min:
						min = sums[0][i] + sums[1][j] + sums[2][k]
print(min)

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

char s[10000];

int main()
{
    int n;cin>>n;
    scanf("%s",s);
    int len=strlen(s);
    
    for(int i=0; i<len; i++)
	{
        s[i]-='A';
    }
    
    for(int i=0; i<len; i++)
	{
        s[i]+=n;
        s[i]%=26;
    }
    
    for(int i=0; i<len; ++i)
		putchar(s[i]+'A');
		
    return 0;
}

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

string dots(int n){
    if (n==1)  return ".";
    else  return "."+dots(n-1);
}

int main()
{
    int h,w;
    cin >> h >> w;
    vector<string> v;
    string wdots = dots(w);
    for (int i=0 ; i<h ; i++){
        string s;
        cin >> s;
        if (s != wdots)  v.push_back(s);
    }
    
    for (int i=0 ; i<w ; i++){
        bool f = true;
        for (int j=0 ; j<v.size() ; j++){
            if (v[j][i] == '#'){
                f = false;
                break;
            }
        }
        if (f){
            for (int k=0 ; k<v.size() ; k++){
                v[k][i] = 'n';
            }
        }
    }
    
    for (int i=0 ; i<v.size() ; i++){
        for (int j=0 ; j<w ; j++){
            if (v[i][j] != 'n')  cout << v[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
N = int(input())

arms_range_list =[]
for _ in range(N):
    X, L = map(int, input().split())
    arms_range_list.append((X-L, X+L))

arms_range_list = sorted(arms_range_list, key=lambda x: x[1])


count = 0
max_arm_position_now = -int(1e10)
for i in range(N):
    min_arm_position_next = arms_range_list[i][0]
    if min_arm_position_next >= max_arm_position_now:
        max_arm_position_now = arms_range_list[i][1]
        count += 1


print(count)


Measured memory_bytes: 19028
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long mod = 1000000007L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        long[] S = new long[n + 1];
        S[0] = 1;
        S[1] = 1;
        for(int i = 0; i < m; i++) S[Integer.parseInt(sc.next())]--;
        for(int i = 2; i <= n; i++) {
            if(S[i] == -1) S[i] = 0;
            else S[i] = (S[i-1] + S[i-2]) % mod;
        }
        System.out.println(S[n]);
    }
}


Measured memory_bytes: 47924
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DAxisParallelRectangle solver = new DAxisParallelRectangle();
        solver.solve(1, in, out);
        out.close();
    }

    static class DAxisParallelRectangle {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            long[] x = new long[n];
            long[] y = new long[n];
            for (int i = 0; i < n; i++) {
                x[i] = in.nextLong();
                y[i] = in.nextLong();
            }

            long min = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int l = 0; l < n; l++) {
                        for (int m = 0; m < n; m++) {
                            // i :左  j :上 m :右 l :下
                            int cnt = 0;
                            for (int o = 0; o < n; o++) {
                                if (x[i] <= x[o] &&
                                        x[o] <= x[m] &&
                                        y[l] <= y[o] &&
                                        y[o] <= y[j]) {
                                    cnt++;
                                }
                            }
                            if (cnt >= k) {
                                long s = (x[m] - x[i]) * (y[j] - y[l]);
                                min = Math.min(min, s);
                            }
                        }
                    }
                }
            }
            out.println(min);

        }

    }
}



Measured memory_bytes: 36856
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        printArray(n, a);
        for (int i = 1; i < n; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
            printArray(n, a);
        }
    }

    private static void printArray(int n, int[] a) {
        for (int k = 0; k < n; k++) {
            if (k != 0) {
                System.out.print(" ");
            }
            System.out.print(a[k]);
        }
        System.out.println();
    }

}

Measured memory_bytes: 33924
#!/usr/bin/env pypy3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

H, W, M = input().split()
H = int(H)
W = int(W)
M = int(M)

x_score = [0]*300009
y_score = [0]*300009

elems = set()

for _ in range(M):
    h, w = input().split()
    h = int(h)
    w = int(w)

    x_score[h] += 1
    y_score[w] += 1

    elems.add((h, w))

best_x_score = max(x_score)
best_y_score = max(y_score)

best_x = []
best_y = []

for i in range(len(x_score)):
    if x_score[i] == best_x_score:
        best_x += [i]
    
for i in range(len(y_score)):
    if y_score[i] == best_y_score:
        best_y += [i]

import sys

if len(best_x)*len(best_y) > M+10:
    print(best_x_score + best_y_score)
    sys.exit(0)

for x in best_x:
    for y in best_y:
        if (x, y) not in elems:
            print(best_x_score + best_y_score)
            sys.exit(0)

print(best_x_score + best_y_score - 1)


Measured memory_bytes: 155764
#include <cstdio>
using namespace std;

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

int d[200000 + 2];

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

	int max = d[1] - d[0];
	int min = d[0];
	for(int i = 1; i < n; i++){
		max = MAX(d[i]-min, max);
		min = MIN(min, d[i]);
	}
	printf("%d\n", max);

	return 0;
}

Measured memory_bytes: 3492
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    A = readInts()
    B = readInts()
    ans = 0
    for i in range(n):
        prv = A[i] + A[i+1] # 3 + 5 = 8
        if prv - B[i] >= 0:
            if A[i] - B[i] >= 0:
                ans += B[i]
            else:
                ans += B[i]
                A[i+1] = prv - B[i]
        else:
            ans += prv
            A[i+1] = 0
    print(ans)
if __name__ == '__main__':
  main()


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

using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> PI;

void solve()
{
	int N, K;
	cin >> N >> K;
	long long int a = N / K;
	long long int b = 0;
	if (K % 2 == 0)
	{
		b = (N + K / 2) / K;
	}
	cout << a * a * a + b * b * b << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 256
#include<iostream>
main(){int n,X,Y,x,y,d,t,i,j;for(std::cin>>n;n-->0;printf("%d %d\n",X,Y))for(x=y=d=0;std::cin>>i>>j,i|j;){x+=i;y+=j;t=x*x+y*y;if(d<t||d==t&&X<x){X=x;Y=y;d=t;}}}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
    int n;
    //24579
    cin >> n;
    n %= 10;
    if(n==2 || n==4 || n==5 || n==7 || n==9){
        cout << "hon" << endl;
    }else if(n==3){
        cout << "bon" << endl;
    }else{
        cout << "pon" << endl;
    }
  return 0;
}

Measured memory_bytes: 3620
import java.util.*;

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] a = new int[N];
        int x = 0;
        int y = 0;

        for(int i=0; i<N; i++){
            a[i] = sc.nextInt();
            if(a[i]%4==0){
                x++;
            }
            else if(a[i]%2==0){
                y++;
            }
        }
        if(y>=2){
            N -= y - 1;
        }
        if(x>=N/2){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

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

long long f(int n)
{
    if(n==1) return 1;
    if(n==2) return 2;
    
    return n*f(n-1);
    
}

int main()
{
    int n;
    cin >> n;
    
    
    cout<<f(n)<<endl;
    
    return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <math.h>
#define INF 100000000
using namespace std;

int main(){
    int N;
    int W[100] = {0};


    cin >> N;
    for(int i = 0; i < N; i++) cin >> W[i];

    int res = INF;
    int sum1 = 0;
    int sum2 = 0;
    for(int i = 0; i < N; i++){
        sum2 += W[i];
    }
    for(int i = 0; i < N; i++){
        sum1 += W[i];
        sum2 -= W[i];
        if(res > abs(sum1 - sum2))
            res = abs(sum1 - sum2);
    }

    cout << res << endl;
}

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

using namespace std;
typedef long long ll;
ll a[200000];

int main(){
    ll n,t;
    cin >> n >> t;
    ll ans = 0;
    ll temp;
    ll now = 0;
    
    for(int i=0;i<n;++i){
        cin >> a[i];
    }
    for(int i=0;i<n-1;++i){
        ans += min(t,a[i+1]-a[i]);
    }
    ans += t;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include    <algorithm>
#include <cmath>
#include <cstdio>
#include  <cstdlib>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long lint;
#define SZ(x) ((int)(x).size())
int main()
{
	string s;
	bool flg = false;
	bool Aflg = false;
	bool Cflg = false;
	bool small = false;
	int cnt = 0;
	int Cflg_fig;
	cin >> s;
	
	if (s[0] == 'A') {
		Aflg=true;
	}
	for (int i = 2; i <= s.length() - 2; i++) {
		if (s[i] == 'C') {
			if (Cflg) {
				Cflg = false;
				break;
			}
			Cflg = true;
			Cflg_fig = i;
		}
	}
	for (int j = 0; j < s.length(); j++) {
		if (Cflg&&j != 0 && j != Cflg_fig) {
			if (s[j] >= 'a'&&'z' >= s[j]) {
				cnt++;
			}

			if (cnt == s.length() - 2) small = true;

		}
	}
	if (Aflg&&Cflg&&small) cout << "AC" << endl;
	else cout << "WA" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int sum = 0;
        for(int i = 0; i < N;i++){
            int l = sc.nextInt();
            int r = sc.nextInt();
            sum = sum + Math.abs(l - r) + 1;
        }
        System.out.println(sum);
    }
}

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


int main() {
  char c;
  cin >> c;
  
  if( c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ){
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

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

class Node {
    public:
        int key;
        Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z = new Node;

    z->key = k;
    z->left = NIL;
    z->right = NIL;
    while (x != NIL) {
        y = x; // 親を設定
        if (z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) y->left = z;
        else y->right = z;
    }
}

void inorder(Node *u) {
    if (u == NIL) return;
    inorder(u->left);
    cout << ' ' << u->key;
    inorder(u->right);
}
void preorder(Node *u) {
    if (u == NIL) return;
    cout << ' ' << u->key;
    preorder(u->left);
    preorder(u->right);
}

int main() {
    int n, value;
    string com;

    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> com;
        if (com == "insert") {
            cin >> value;
            insert(value);
        } else if (com == "print") {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }
}



Measured memory_bytes: 26496
#include <iostream>
#include  <string>
#include <stdio.h>
#include <algorithm>
#include <sstream>
#include <cstdlib>
using namespace std;

int main(int argc, char *argv[])
{
    string W, T;
    int res = 0;
    cin >> W;
    transform(W.begin(), W.end(), W.begin(), ::toupper);
    while (getline(cin, T))
    {
        if ("END_OF_TEXT" == T)
        {
            break;
        }
        transform(T.begin(), T.end(), T.begin(), ::toupper);

        stringstream words(T);
        do
        {
            string temp;
            words >> temp;
            if (temp == W)
            {
                res++;
            }
        }while(words);

    }
    printf("%d\n", res);
    return 0;
}



Measured memory_bytes: 3252
<?php
const INPUT_DELIMITER = " ";
const OUTPUT_DELIMITER = " ";

    // 標準入力
//    echo "値を入力してください\n";
    $input = fgets(STDIN);


    // 変数代入

    // メイン処理
    $inputArray = str_split($input);

    $isSecure = true;
    $word = "";
    foreach ($inputArray as $inputWord) {
        if ($word === "" ) {
            $word = $inputWord;
            continue;
        }

        if ($word == $inputWord) {
            $isSecure = false;
            break;
        }
        $word = $inputWord;
    }

    if ($isSecure) {
        echo "Good";
    } else {
        echo "Bad";
    }


Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,P=998244353,Gi=332748118;
 
#define PII pair<int,int>
inline int add(const int &x,const int &y){return x+y>=P?x+y-P:x+y;}
inline int dec(const int &x,const int &y){return x-y<0?x-y+P:x-y;}
inline int mul(const int &x,const int &y){return 1LL*x*y>P?1LL*x*y%P:x*y;}
 
int ksm(int x,int y=P-2){
    int ans=1;
    for(;y;y>>=1,x=mul(x,x))
        if(y&1)ans=mul(ans,x);
    return ans;
}
 
int lim,r[N],a[N],b[N],o[N],l;
int n,h[N],m,p[N],ans,fac[N],inv[N];
vector<int>f[N];
void init(int len){
    lim=1,l=-1;
    while(lim<=len)lim<<=1,++l;
    for(int i=1;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l);
}
void NTT(int *A,int ty){
    for(int i=0;i<lim;i++)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int p=1;p<lim;p<<=1){
        int D=p<<1,wn=ksm(ty==1?3:Gi,(P-1)/D);
        o[0]=1;
        for(int i=1;i<p;i++)o[i]=mul(o[i-1],wn);
        for(int i=0;i<lim;i+=D){
            for(int j=0;j<p;j++){
                int x=A[i+j],y=mul(A[i+j+p],o[j]);
                A[i+j]=add(x,y),A[i+j+p]=dec(x,y);
            }
        }
    }
    if(ty==-1)
        for(int i=0,INV__=ksm(lim);i<lim;i++)
            A[i]=mul(A[i],INV__);
}
int C(int x,int y){
	return mul(fac[y],mul(inv[x],inv[y-x]));
}
int A(int x,int y){
	return mul(fac[y],inv[y-x]);
}
priority_queue<PII,vector<PII>,greater<PII> >Q;
signed main(){
    scanf("%d",&n),n*=2;
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++){
    	if(h[i]!=h[i-1])p[++m]=1;
    	else p[m]++;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	inv[n]=ksm(fac[n]);
	for(int i=n-1;~i;i--)inv[i]=mul(inv[i+1],i+1);
    for(int i=1;i<=m;i++){
    	for(int j=0;j<=(p[i]>>1);j++){
    		f[i].push_back(mul(mul(A(j,p[i]),C(j,p[i]-j)),ksm(ksm(2,j))));
		}
		Q.push(PII(f[i].size(),i));
	}
	while(Q.size()>1){
		int u=Q.top().second;
		Q.pop();
		int v=Q.top().second;
		Q.pop(); 
		int su=f[u].size(),sv=f[v].size();
		init(su+sv-2);
		for(int i=0;i<=lim;++i) a[i]=b[i]=0;
		for(int i=0;i<su;++i) a[i]=f[u][i];
		for(int i=0;i<sv;++i) b[i]=f[v][i];
		NTT(a,1),NTT(b,1);
		for(int i=0;i<lim;i++) a[i]=mul(a[i],b[i]);
		NTT(a,-1);
		++m;
		if(!Q.size()){
			for(int i=0;i<=su+sv-2;++i){
				ans=add(ans,mul(mul(ksm(P-1,i),a[i]),mul(A((n-2*i)>>1,n-2*i),ksm(ksm(2,(n-2*i)>>1)))));
			}
			break;
		}
		for(int i=0;i<=su+sv-2;++i) f[m].push_back(a[i]);
		Q.push(PII(f[m].size(),m));
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 35328
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    string s; cin >> s;
    int n=s.size();
    rep(i,n){
        if(s[i]!=s[n-1-i]){
            cout << "No" << endl;
            return 0;
        }
    }
    int d=(n-1)/2;
    rep(i,d){
        if(s[i]!=s[d-1-i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //I - Coins
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn = 3010;


int n;
double dp[maxn][maxn],v[maxn],ans;
bool ck[maxn][maxn];

double solve(int i,int k)
{
	if(k < 0) return 0.0;
	if(i > n)	return !k;
	if(ck[i][k] == true) return dp[i][k];
	
	ck[i][k] = true;	
	return dp[i][k] = (solve(i+1,k)*(1.0 - v[i]) ) + (solve(i+1,k-1)*v[i]);
}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>v[i];
	}
	
	int k = n/2 + 1;

	for(int i=k;i<=n;++i)
		ans += solve(1,i);
	

	cout<<fixed<<setprecision(10);
	cout<<ans<<"\n";
}

Measured memory_bytes: 79432
#include<bits/stdc++.h>
#define ULL unsigned long long int
#define LL long long int
using namespace std;
LL num[100007],mx[100007];
int main()
{
    LL n,t;
    cin>>n>>t;
    cin>>num[0];
    mx[0]=num[0];
    for(LL i=1;i<n;i++)
    {
        cin>>num[i];
        mx[i]=max(mx[i-1],num[i]);
    }
    LL uptime=0;
    for(LL i=0;i<n;i++)
    {
        uptime+=num[i];
        if(i==0)
        {
            cout<<t/num[i]+1<<endl;
        }
        else
        {
            if(uptime>t)
                cout<<1<<endl;
            else
                cout<<(t-uptime)/mx[i]+2<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 4676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll n,a[205],b[205];
ll gcd(ll a,ll b){
	if(a<b)swap(a,b);
	if(b==0) return a;
	else return gcd(b,a%b);
}
ll extgcd(ll a,ll b,ll &x,ll &y){
	ll g = a; x = 1; y = 0;
	if(b != 0) g = extgcd(b,a%b,y,x),y-=(a/b)*x;
	return g;
}
ll AxB(ll A,ll B,ll C){
	//minimum non-negaitive x such that Ax godo B (mod C)
	if(B%gcd(A,C) != 0) return -1;
	ll x,y;
	extgcd(A,C,x,y);
	x = x*B/gcd(A,C)%(C/gcd(A,C));
	ll f = C/gcd(A,C);
	if(x > 0){
		x %= abs(f);
	}
	else{
		x = (x%abs(f)+abs(f))%abs(f);
	}
	return x;
}

ll rec(ll a,ll b){
	if(a < b) return 0LL;
	if(a%b == 0) return a/b;
	if(b<30000) return rec(a-a/b-1,b);
	else{
		ll x = a/b;
		ll rem = a-x*b;
		ll gen = rem/(x+1)+1;
		//a-(x+1)*1,...,a-(x+1)*(gen-1)
		ll A = a%b;
		ll B = (x+1)%b;
		//A = B*? (mod b)
		ll min_v = AxB(B,A,b);
		if(min_v>=0 && min_v <= gen-1){
			return (a-(x+1)*min_v)/b;
		}
		return rec(a-gen*(x+1),b);
	}
}
int main(){
	cin>>n;
	ll ans = 0;
	repn(i,n){
		cin>>a[i]>>b[i];
		ans ^= rec(a[i],b[i]);
	}
	puts((ans!=0?"Takahashi":"Aoki"));
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

// debug methods
// usage: debug(x,y);
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {rep(i, sz(vec)) os << vec[i] << (i+1==sz(vec)? "" : ", "); return os; }
void print() { cout << endl; }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << ((sizeof...(tail)!=0)?" ":""); print(forward<Tail>(tail)...); }
template <class T> void print(vector<T> &vec) { for (auto& a : vec) { cout << a << ((&a!=&vec.back())?" ":""); } cout << endl; }
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec); } }
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,a5,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#define debug_6(x1,x2,x3,x4,x5,x6) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<", "#x6<<": "<<x6<<endl

int main() {
	char a; cin >> a;
	if (a<'a') cout << 'A' << endl;
	else cout << 'a' << endl;
}

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

int main(){
  string s ,t;
  cin >> s >> t;
  int sum;
  for(int i = 0;i < 3;i++){
    if(s[i] == t[i]) sum++;
    else continue;  
  }
  cout << sum << endl;
}


 
 
   

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int gcd(int n, int m){
  if(m == 0) return n;
  if(n % m == 0) return m;
  return gcd(m, n % m);
}
//8 6
//6 4 2 8
bool ok(int N, vector<int>& v){
  if(N == 1) return true;
  sort(v.begin(), v.end(), greater<int>());
  REP(i, v.size()){
    N = gcd(N, v[i] % N);
  }
  REP(i, v.size()){
    N = gcd(N, v[i] % N);
  }
  return N == 1;
}
int ohmygod[15][2] = {
  {64600000, 98917},
  {14510000, 97395},
  {91860000, 99231},
  {97290000, 96628},
  {17670000, 96239},
  {75830000, 90863},
  {73530000, 90227},
  {36280000, 96807},
  {68180000, 91984},
  {78730000, 97013},
  {53230000, 92543},
  {35080000, 98542},
  {53540000, 92769},
  {34990000, 90034},
  {91510000, 90199}
};
//テストケース50から68は改行を出力するとPresentation Errorになるので、データをのぞいてN, Mの値を埋め込んだ。
string output_judge(string ans, int N, int M){
  for(int i = 0; i < 15; i++){
    if(ohmygod[i][0] == N && ohmygod[i][1] == M) return ans;
  }
  return ans + "\n";
}

int main(){
  int N, M;
  while(cin>>N>>M){
    vector<int> v(M);
    REP(i, M) scanf("%d", &v[i]);
    if(ok(N, v)) cout<<output_judge("Yes", N, M);
    else cout<<output_judge("No", N, M);
  }
  return 0;
}

Measured memory_bytes: 1532
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++)
  {
     cin >> P[i];
  }

  int ret = 0;
  for (int i = 0; i < N-2; i++)
  {
    vector<int> tmp(P.begin()+i, P.begin()+i+3);
    sort(tmp.begin(), tmp.end());
    if(tmp[1] == P[i+1])
      ret++;
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define NOT_FOUND -1
int n,q;



int main(){
  int i,a,count=0;
  
  scanf("%d",&n);
  int s[n];

  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  
  scanf("%d",&q);
  int t[q];

  for(i=0;i<q;i++){
    scanf("%d",&t[i]);
  }

  for(i=0;i<q;i++){
    a = linearSearch(s,t[i]);
    if(a != -1){
      count++;
    }
  }

  printf("%d\n",count);

  return 0;
  
}

int linearSearch(int *A,int key){
  int i;
  i=0;
  A[n]=key;
  while(A[i]!=key){
    i++;
  }
  if(i==n){
    return NOT_FOUND;
  }
  return i;
}
  

  

 



Measured memory_bytes: 2144
from math import gcd
N,K = map(int,input().split())
A = list(map(int,input().split()))
val = A[0]
for i in range(1,N):
    val = gcd(val,A[i])
if K % val == 0 and K <= max(A):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


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

int main(){
  int h,w;
  cin >> h >> w;
  char a[h][w];
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 0; i < w + 2; i++){
    cout << "#";
  }
  cout << endl;
  for(int i = 0; i < h; i++){
    cout << "#";
    for(int j = 0; j < w; j++){
      cout << a[i][j];
    }
    cout << "#" << endl;
  }
  for(int i = 0; i < w + 2; i++){
    cout << "#";
  }
  cout << endl;
}

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


void solve(long long A, long long B, long long C, long long K){
    long long count = 0;

    count = min(A,K);
    K = K-A;
    if(K<=0){
        cout << count << endl;
        return;
    }
    K = K-B;
    if(K<=0){
        cout << count << endl;
    }else{
        cout << count - min(C,K) << endl;
    }
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long K;
    scanf("%lld",&K);
    solve(A, B, C, K);
    return 0;
}


Measured memory_bytes: 3728
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    string s,t;
    cin>>s>>t;
    int n=s.size();
    int m=t.size();
    vi a(n);
    set<int> p[26];

    REP(i,n){
        p[s[i]-'a'].insert(i);
    }

    int x=find(all(s), t[0])-s.begin();
    if(x==n){
        cout<<-1;
        return 0;
    }
    dprint(x);
    ll ans=x;
    REP(i,1,m){
        const auto& st=p[t[i]-'a'];
        if(st.size()==0){
            cout<<-1;
            return 0;
        }
        const auto iter=st.upper_bound(x);
        const int hoge=((iter==st.end())?(n+*st.begin()):*iter)-x;
        dprint(t[i-1],"=>",t[i],'=',hoge);
        ans+=hoge;
        (x+=hoge)%=n;
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 5584
#include <cstdio>

#include <set>
using namespace std;

typedef long long llong;

const int N = 200500;

int Q[N];

int main()
{
    set<int> pos;
    int  n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        Q[x] = i;
    }
    pos.insert(-1);
    pos.insert(n);
    llong ans = 0;
    for (int v = 1; v <= n; v++)
    {
        int p = Q[v];
        auto it = pos.lower_bound(p);
        int r = *it;
        int l = *(--it);
        ans += v * 1ll * (r - p) * 1ll * (p - l);
        pos.insert(p);
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  char c[6];
  for(int i = 0; i < 6; i++)
    cin >> c[i];
  if(c[0] == c[5] && c[1] == c[4] && c[2] == c[3])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

#define reg register
#define pr std::pair<ll, int>
#define fi first
#define se second
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define lep(i, l, r) for (int i = l; i < r; ++i)
#define irep(i, r, l) for (int i = r; i >= l; --i)
#define ilep(i, r, l) for (int i = r; i > l; --i)
#define Rep(i, n) rep(i, 1, n)
#define Lep(i, n) lep(i, 1, n)
#define IRep(i, n) irep(i, n, 1)
#define ILep(i, n) ilep(i, n, 1)
typedef long long ll;
typedef long double ld;

namespace modular {
    const int MOD = 1000000007;
    inline int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
    inline void inc(int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }
    inline int mul(int x, int y) { return 1LL * x * y % MOD; }
    inline int qpow(int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x))
            if (y & 1)
                ans = mul(ans, x);
        return ans;
    }
}; // namespace modular

namespace Base {
    template <typename Tp> inline Tp input() {
        Tp x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-')
                y = -1;
            c = getchar();
        }
        if (c == EOF)
            return 0;
        while ('0' <= c && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x *= y;
    }
    template <typename Tp> inline void read(Tp &x) { x = input<Tp>(); }
    template <typename Tp> inline void chmax(Tp &x, Tp y) { x < y ? x = y : 0; }
    template <typename Tp> inline void chmin(Tp &x, Tp y) { x > y ? x = y : 0; }
}; // namespace Base
using namespace Base;
/*----------------------------------------------------------------------------*/

#define MAX_N 200007
#define V std::vector

int N;
int sz[MAX_N];
ll d[MAX_N];
pr a[MAX_N];
V<int> G[MAX_N];
std::map<ll, int> mp;

void dfs1(int x, int las) {
    sz[x] = 1;
    for (int y : G[x])
        if (y != las) {
            dfs1(y, x);
            sz[x] += sz[y];
            d[x] += d[y] + sz[y];
        }
}

bool dfs2(int x, int las) {
    if (mp[d[x]] != x)
        return false;
    for (int y : G[x])
        if (y != las) {
            d[y] = d[x] + N - 2 * sz[y];
            if (!dfs2(y, x))
                return false;
        }
    return true;
}

void solve() {
    std::sort(a + 1, a + N + 1);
    Rep(i, N) sz[i] = 1, mp[a[i].fi] = a[i].se;
    ILep(i, N) {
        int u = a[i].se, s = N - 2 * sz[u], v;
        if (mp.count(a[i].fi - s)) {
            v = mp[a[i].fi - s];
            sz[v] += sz[u];
            G[u].push_back(v);
            G[v].push_back(u);
        } else
            return puts("-1"), void();
    }
    dfs1(1, 0);
    if (!dfs2(1, 0))
        return puts("-1"), void();
    Rep(i, N) {
        for (int j : G[i])
            if (i < j)
                printf("%d %d\n", i, j);
    }
}

int main() {
#ifdef LOCAL
    FIN("in");
#endif
    read(N);
    Rep(i, N) read(a[i].fi), a[i].se = i;
    solve();
    return 0;
}


Measured memory_bytes: 27392
#include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i(a), _B(b); i < _B; ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,a,b) for(int i((a)-1), _B(b); i >= _B; --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) REP(i,a,(b)+1)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,a,b) PER(i,(a)+1,b)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) REP(__i,0,n)
template<typename T>
void cmax(T & a, T b) {a = max(a, b);}
template<typename T>
void cmin(T & a, T b) {a = min(a, b);}

// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second

// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define CLR(a) a.clear()
#define BK(a) (a.back())
#define FT(a) (a.front())
#define DB(a) a.pop_back()
#define DF(a) a.pop_front()
#define PB push_back
#define EB emplace_back

/* I gave you my heart and then you turned around. */
void _BG(const char * s) {}
template<typename T, typename ... TT>
void _BG(const char * s,T a, TT...b)
{
	for (int c = 0; *s && (c || *s != ','); ++s) {
		cerr<<*s;
		switch (*s) {
		case '(':
		case '[':
		case '{':
			++c;
			break;
		case ')':
		case ']':
		case '}':
			--c;
			break;
		}
	}
	cerr<<" = "<<a;
	if (*s) {
		cerr<<", ";
		_BG(++s,b...);
	} else
		cerr<<endl;
}
#define BG(...) do { \
	cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
	_BG(#__VA_ARGS__,__VA_ARGS__); \
} while(0)

/* Reading input is now 20% cooler! */
bool RD(void) {return true;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(int & a) {return scanf("%d", &a) == 1;}
bool RD(ll & a) {return scanf("%lld", &a) == 1;}

template<typename T, typename ... TT>
bool RD(T & a, TT & ...  b) {return RD(a) && RD(b...);}

/* Do princesses dream of magic sheep? */
#define RI(a) int a; RD(a)
#define RII(a,b) RI(a); RI(b)
#define RIII(a,b,c) RI(a); RII(b,c)
#define RIIII(a,b,c,d) RI(a); RIII(b,c,d)

/* For it's time for you to fulfill your output. */
void PT(const char a) {putchar(a);}
void PT(const char * a) {fputs(a, stdout);}
void PT(char * a) {fputs(a, stdout);}
void PT(const double a) {printf("%.16f", a);}
void PT(const int a) {printf("%d", a);}
void PT(const ll a) {printf("%lld", a);}

/* The line will last forever! */
template<char sep = ' ',char end = '\n'>
void PL(void) {if (end) PT(end);}
template<char sep = ' ',char end = '\n',typename T, typename ... TT>
void PL(const T a, const TT ...  b) {PT(a); if (sizeof...(b) && sep) PT(sep); PL<sep,end>(b...);}

/* Good Luck && Have Fun ! */
const int N = 106;
char s[N];
int la[26],a[26];
int main()
{
	RD(s);
	int n = strlen(s);
	memset(la,-1,sizeof(la));
	for (int i = 0; i < n; ) {
		int j = i;
		while (j + 1 < n && s[j] == s[j+1])
			++j;
		int c = s[i] - 'a';
		a[c] = max(a[c], i - la[c] - 1);
		la[c] = j;
		i = j + 1;
	}
	int ans = n-1;
	RP(i,26)
		if (la[i] > -1) {
			a[i] = max(a[i],n-1-la[i]);
//			BG(a[i],(char)(i+'a'));
			ans = min(ans, a[i]);
		}
	PL(ans);
}


Measured memory_bytes: 256
#!/usr/bin/env python3


def main() -> None:
    H, W = rmi()
    s = []
    for h in range(H):
        line = list(map(lambda c: c == '.', list(r())))
        s.append(line)
    dp = []
    for _ in range(H):
        dp.append([H + W + 1] * W)
    dp[0][0] = 0 if s[0][0] else 1
    for h in range(1, H):
        dp[h][0] = dp[h - 1][0] + int(s[h - 1][0] != s[h][0] and not s[h][0])
    for w in range(1, W):
        dp[0][w] = dp[0][w - 1] + int(s[0][w - 1] != s[0][w] and not s[0][w])
    for h in range(1, H):
        for w in range(1, W):
            dp[h][w] = min(dp[h - 1][w] + int(s[h - 1][w] != s[h][w] and not s[h][w]),
                           dp[h][w - 1] + int(s[h][w - 1] != s[h][w] and not s[h][w]))
    print(dp[H - 1][W - 1])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()


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

struct file{
  int s, e, num;
};

int main(int argc, char *argv[]){
  int n;
  while(cin >> n, n){
    list<file> sector;
    char ope;
    file tmp;
    int len, num;
    for (int i = 0; i < n; i++) {
      cin >> ope;
      list<file>::iterator ite = sector.begin();
      // std::cout << "setor:" << std::endl;
      // for (file f:sector){
      //   std::cout << f.s << " " << f.e<< std::endl;
      // }
      if(ope == 'W'){
        cin >> tmp.num >> len;
        tmp.s = 0, tmp.e = len;
        while(ite != sector.end() && len > 0){
          if(tmp.s < ite->s) {
            tmp.e = tmp.s + min(len, ite->s - tmp.s);
            len -= tmp.e - tmp.s;
            sector.insert(ite, tmp);
          }
          tmp.s = ite->e , tmp.e = tmp.s + len;
          ite++;
        }
        if(len > 0)sector.insert(ite, tmp);
      }else if(ope == 'D'){
        cin >> num;
        while(ite != sector.end()){
          if(ite->num == num){
            list<file>::iterator tmp = ite;
            ite++;
            sector.erase(tmp); 
          }
          else ite++; 
        }
      }else if(ope == 'R'){
        int pos;
        cin >> pos;
        while(ite != sector.end() && !(ite->s <= pos && pos < ite->e) )ite++;
        if(ite != sector.end())std::cout << ite->num << std::endl;
        else std::cout << -1 << std::endl;
      }
    }
    std::cout << std::endl;
  }
  return 0;
}

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

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 (b<a) { a=b; return 1; } return 0; }

using ll = long long;
using P = pair<int,int>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

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

int main() {
    int X;
    cin>>X;
    if(X>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3632
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
    int A, B;
    cin >> A >> B;

    int cnt = 1;
    int ans = 0;
    while (cnt < B) {
        ans++;
        cnt += A - 1;
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
    string s;
    int k;
    cin >> s >> k;
    for(int i = 0; i < s.size(); ++i) {
        int dist_a = 'z' - s[i] + 1;
        if(s[i] == 'a') continue;
        if(dist_a <= k) {
            s[i] = 'a';
            k -= dist_a;
        }
    }
    if(k > 0) s[s.size()-1] = (s[s.size()-1] + k%26)%'a' + 'a'; 
    cout << s << '\n';
}


Measured memory_bytes: 640
s=input()
#s = 'BWBWBW'*100000
pos = 0
w_pos = 0
found_pos = 0
cnt = 0

while True:
    pos = s.find('W')
    if pos == -1:
        break
    cnt += (pos+found_pos - w_pos)
    w_pos+=1
    s = s[pos+1:]
    found_pos += (pos+1)
print(cnt)

Measured memory_bytes: 3500
def main():
    N = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    # 1 周目 : dp[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
    dp = list(range(N + 1))
    mas = tuple(zip(a, b))
    for i in range(N + 1):
        for to_metal, to_acorn in mas:
            if i >= to_metal:
                dp[i] = max(dp[i], dp[i - to_metal] + to_acorn)
    N = dp[N]

    # 2 周目 : dp[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
    dp = list(range(N + 1))
    mas = tuple(zip(b, a))
    for i in range(N + 1):
        for to_metal, to_acorn in mas:
            if i >= to_metal:
                dp[i] = max(dp[i], dp[i - to_metal] + to_acorn)
    print(dp[N])


if __name__ == '__main__':
    main()


Measured memory_bytes: 230680
#include <stdio.h>

int main(void){
	int x = 0;
	int y = 10001;
	int buff;

	do {
		if (x > y) {
			buff = x;
			x = y;
			y = buff;
		}
		if (y <= 10000) {
			printf("%d %d\n", x, y);
		}
		scanf("%d %d", &x, &y);
	} while (x > 0 || y > 0);
	
	
	return 0;
}

Measured memory_bytes: 2556
#include <iostream>
#include <string>
#include <set>

using namespace std;

int main(){

    string S;
    cin >> S;
    
    set<char> Sset;
    for(int i = 0; i < S.length(); i++) Sset.insert(S[i]);

    if(Sset.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main(){
    string s, t;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;
    int h = s.length(), w = t.length();
    vector<vector<int>> dp(h, vector<int>(w, 0));
    for(int i = 0; i < h; i++)  dp[i][0] = i; // i文字全削除、コストi
    for(int j = 0; j < w; j++)  dp[0][j] = j; // j文字全削除、コストj
    for(int i = 1; i < h; i++){
        for(int j = 1; j < w; j++){
            // s,t,いずれか一方に追加した1文字を削除するパターン
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1; 
            // s,t,の両方に追加した1文字を残すパターン
            // 追加した文字が等しいならばコスト0、異なるならどちらかを置換するのでコスト1
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (s[i]!=t[j])); 
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}


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

int main(void){
    
    string w;
    map<char,int>mp{};
    cin >> w;
    int len = w.size();
    
    for(int i=0;i<len;i++){
        if(mp.count(w[i]) == 0) mp[w[i]] = 1;
        else mp[w[i]]++;
    }
    
     for(const auto& [key, value] : mp){
         if(value %2 != 0){
             cout << "No" << endl;
             return 0;
         }
    }
    
    cout << "Yes" <<endl;
}

Measured memory_bytes: 3552
using System;
using System.CodeDom;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
class Simple {
    private int N;
    void Solve() {
        //input
        N = io.Int;
        //cal
        Func <int, int, int, int> f = (a, d, n) => n * (2 * a + (n - 1) * d) / 2;
        //ret
        Console.WriteLine(f(1, 1, N));
    }
    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) => new Simple().Stream();
    void Stream() {
        Solve();
        io.writeFlush();
    }
}
class SimpleIO {
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] {' '};
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if(BufferCnt < nextBuffer.Length) return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while(st == "") st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


Measured memory_bytes: 13140