akhauriyash/Code-Regression huggingface dataset:
import math
import bisect
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,5000)]
while top<math.sqrt(10000):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist
while(1):
    try:
        n=int(raw_input())
    except:
        break
    if n%2==0:
        if n-1 in primes:
            print 2
        else:
            print 0
    else:
        ans=0
        center=(n+1)/2
        distc=[x-center for x in primes[:bisect.bisect(primes,n)]]
        if 0 in distc:
            ans=1
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)+1
        else:
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)
        while(il>=0 and ir<len(distc)):
            if distc[il]+distc[ir]==0:
                ans=ans+2
                il=il-1
                ir=ir+1
            elif distc[il]+distc[ir]<0:
                ir=ir+1
            else:
                il=il-1
        print ans

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

const ll INF = ll(1e18)+1;

//①適当な中央の値xを作って
//②x未満の値が何個あるか求める
//③繰り返して言ってlとrが隣あう数字になれば終了

int main(){
    int n; ll k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    ll l = -INF, r = INF;
    //lとrが隣り合ったら終了
    while (l+1 < r) {
        //2文探索の中央の値
        ll x = (l+r)/2;
        //xがokかどうかを判定(ラムダ関数)
        //[&]を用いると外の関数にアクセスできる
        bool ok = [&]{
            ll tot = 0;
            rep(i,n) {
                if (a[i] < 0) {
                    int l = -1, r = n;
                    while (l+1<r) {
                        int c = (l+r)/2;
                        //負の場合、変わるのはここだけ。
                        //rとlが逆に動く
                        if(a[c]*a[i] < x) r = c; else l = c;
                    }
                    tot += n-r;
                } else {
                    //ベクトルaのインデックスの定義
                    //仮に全て相方になれないとしたらr=0になる、okがいないのがl=-1、全てokでl=n-1
                    int l = -1, r = n;
                    //幅が1になるまで
                    while (l+1<r) {
                        //左端と右端の半分の値を求める
                        int c = (l+r)/2;
                        //x未満のときokである左端の値lをcにする、その逆のときNGである右端の値rをcにする。
                        if (a[c]*a[i] < x) l = c; else r = c;
                    }
                    //l+1(インデックスだから+1)まで
                    tot += r;
                }
                //自分自身を削除
                if (a[i]*a[i] < x) tot--;
            }
            //半分にする
            tot /= 2;
            //今求めたいtotalの個数
            return tot < k;
        }();
        //↑すぐに関数の呼び出し
        //okならlに出力、ngならrに出力
        if(ok) l = x; else r = x;
    }
    //ギリギリokな値lを出力
    cout << l << "\n";
    return 0;
}

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

const int Maxn=1e5;

int N,A[Maxn+5];

int GCD(int a,int b) {
	if(b==0) return a;
	return GCD(b,a%b);
}

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&A[i]);
	int ans=A[1];
	for(int i=2;i<=N;i++)
		ans=GCD(ans,A[i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200003;
const ll INF=1LL<<60;

struct data{
    ll b;
    ll c;
    ll diff;
};

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int X,Y,Z;cin>>X>>Y>>Z;
    int N=X+Y+Z;
    vector<ll> A(N),B(N),C(N);
    ll sum=0;
    for(int i=0;i<N;i++){
        cin>>A[i]>>B[i]>>C[i];
        sum+=A[i];
        B[i]-=A[i];
        C[i]-=A[i];
    }
    
    vector<data> D(N);
    for(int i=0;i<N;i++){
        D[i]={B[i],C[i],B[i]-C[i]};
    }
    
    sort(all(D),[](data a,data b){
        return a.diff>b.diff;
    });
    
    vector<ll> bsum(N+2),csum(N+2);
    
    priority_queue<ll,vector<ll>,greater<ll>> PQ;
    
    for(int i=0;i<Y;i++){
        bsum[i+1]=bsum[i]+D[i].b;
        PQ.push(D[i].b);
    }
    
    for(int i=Y;i<N;i++){
        bsum[i+1]=bsum[i]+D[i].b;
        PQ.push(D[i].b);
        bsum[i+1]-=PQ.top();
        PQ.pop();
    }
    
    while(!PQ.empty()) PQ.pop();
    
    for(int i=0;i<Z;i++){
        csum[N-i]=csum[N-i+1]+D[N-1-i].c;
        PQ.push(D[N-1-i].c);
    }
    
    for(int i=Z;i<N;i++){
        csum[N-i]=csum[N-i+1]+D[N-1-i].c;
        PQ.push(D[N-1-i].c);
        csum[N-i]-=PQ.top();
        PQ.pop();
    }
    
    ll maxi=-INF;
    
    for(int i=Y;N-i>=Z;i++){
        maxi=max(maxi,bsum[i]+csum[i+1]);
    }
    
    cout<<sum+maxi<<endl;
    
}




Measured memory_bytes: 7672
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner teclado = new Scanner(System.in);
		String P = teclado.nextLine();
		int S[] = new int[4];
		for (int x = 0; x < 4; x++) {
			S[x] = P.charAt(x);
		}
			if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
				System.out.println("Bad");
			}
			
			else {
				System.out.println("Good");
			}
		
		
		teclado.close();

	}

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 100005;

int dx[] = {0, -1, 1, 0};
int dy[] = {-1, 0, 0, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    string s;
    cin >> n >> k >> s;
    s[k - 1] = s[k - 1] + ( 'a' - 'A' );
    cout << s << endl;
    return 0;
}



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


using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 1010;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}



// Main Code

ll len[51];
ll ps[51];

ll findans(ll x, int n)
{
	if(x <= 0) return 0;
	ll tlen = len[n];
	if(x >= tlen) return ps[n];
	ll ans = findans(x-1, n-1) + findans(x - (tlen/2) - 1, n-1);
	if(x > (tlen / 2))
		ans++;
	return ans;
}

int main()
{
	ll n, x;
	cin>>n>>x;
	len[0] = ps[0] = 1;
	repn(i, 1, 50)
	{
		len[i] = len[i-1]*2 + 3;
		ps[i] = ps[i-1]*2 + 1;
	}
	cout<<findans(x, n)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define lp(i,n) for(ll i=0;i<n;i++)
using namespace std;
ll min(ll a,ll b){
 return a<b?a:b;
}
int main(){
  ll n;
  cin>>n;
  ll h[n];
  lp(i,n)
    cin>>h[i];
  ll dp[n+1];
  dp[0]=0;
  lp(i,n+1){
    if(i-1>=0)
      dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
    if(i-2>=0)
      dp[i]=min(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout<<dp[n-1]<<endl;
 
	return 0;
}

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

void solve()
{
  long long A, B;
  cin >> A >> B;
  long long g = __gcd(A, B);
  cout << (A * B / g);
}
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(11);
  solve();
  return 0; 
}


Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])

Measured memory_bytes: 7748
n,k = map(int,input().split())
v = list(map(int,input().split()))

p = min(n, k)

res = 0

for i in range(p, -1, -1):
        # kことる
        for l in range(i + 1):
                r = i - l
                # 左からl, 右からrとる
                q = []
                for w in range(l):
                        q.append(v[w])
                for w in range(n - r, n):
                        q.append(v[w])
                q = sorted(q)
                ans = sum(q)
                tmp = ans
                for w in range(min(k - i, len(q))):
                        tmp -= q[w]
                        ans = max(ans, tmp)
                res = max(res, ans)



print(res)

Measured memory_bytes: 3188
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        //long start = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        //long n = sc.nextLong();
        String s = sc.next();
        sc.close();

        int sum = 0;
        for (int i = 0;i<s.length();++i) sum += Integer.parseInt(s.substring(i,i+1));

        if (sum%9 == 0) System.out.println("Yes");
        else System.out.println("No");
//        long end = System.currentTimeMillis();
//        System.err.println((end-start)+"ms");
    }
}

Measured memory_bytes: 49620
#include <stdio.h>
#include <string.h>

#define MAX 1001

typedef struct{
  char X[MAX];
  char Y[MAX];
}Retu;


int main()
{
  int n,xl,yl,i,j,k,c[MAX][MAX];
  
  scanf("%d",&n);

  Retu kumi[n];

  for(i=0;i<n;i++)
    {
      
      scanf("%s",&kumi[i].X);
      scanf("%s",&kumi[i].Y);
    }
  
  for(i=0;i<n;i++)
    {

      xl=strlen(kumi[i].X);
      yl=strlen(kumi[i].Y);

      c[0][0]=0;
      
      for(j=1;j<=xl;j++)c[j][0]=0;
      for(j=1;j<=yl;j++)c[0][j]=0;

      for(j=1;j<=xl;j++)
	{
	  for(k=1;k<=yl;k++)
	    {
	      if(kumi[i].X[j-1]==kumi[i].Y[k-1])
		{
		  c[j][k]=c[j-1][k-1]+1;
		}
	      else if(c[j-1][k]>=c[j][k-1])
		{
		  c[j][k]=c[j-1][k];
		}
	      else
		{
		  c[j][k]=c[j][k-1];
		}
	    }
	}

      printf("%d\n",c[xl][yl]);
    }

  return 0;
}



Measured memory_bytes: 5688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
	int n,weight;
    cin>>n>>weight;
    vector<vector<long long> > cell(n+1,vector<long long>(weight+1,0));
    //vector<vector<vector<int> > > sert();
    for(int i=1;i<=n;i++){
        int w,v;
        cell[i][0]=0;
        cin>>w>>v;
        for(int j=1;j<=weight;j++){
            if(j-w<0){
                cell[i][j]=cell[i-1][j];
                continue;
            }
            cell[i][j]=max(cell[i-1][j],v+cell[i-1][j-w]);
        }
    }
    cout<<cell[n][weight];
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;

#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////

struct range{
    ll l,r;
};

int main(){
    ll n;cin>>n;
    vector<ll>v[n];
    rep(i,1,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        v[a].pb(b);
        v[b].pb(a);
    }
    vector<ll>chi[n];
    ll par[n];rep(i,0,n-1)par[i]=-inf;
    par[0]=-1;
    queue<ll>q;q.push(0);
    vector<ll>ver;
    while(!q.empty()){
        ll t=q.front();q.pop();
        ver.pb(t);
        for(auto x:v[t]){
            if(par[x]==-inf){
                par[x]=t;
                chi[t].pb(x);
                q.push(x);
            }
        }
    }
    reverse(ver.begin(),ver.end());
    range u[n];
    rep(i,0,n-1){
        u[i].l=-inf;u[i].r=inf;
    }
    ll kk;cin>>kk;
    while(kk--){
        ll a,b;cin>>a>>b;
        a--;
        u[a].l=u[a].r=b;
    }
    for(auto x:ver){
        for(auto y:chi[x]){
            Max(u[x].l,u[y].l-1);
            Min(u[x].r,u[y].r+1);
        }
        if(u[x].l>u[x].r){
            cout<<"No"<<endl;
            return 0;
        }
    }
    ll ans[n];
    reverse(ver.begin(),ver.end());
    for(auto x:ver){
        if(u[x].l>u[x].r){
            cout<<"No"<<endl;
            return 0;
        }
        ans[x]=u[x].l;
        u[x].r=u[x].l;
        for(auto y:chi[x]){
            Max(u[y].l,u[x].l-1);
            Min(u[y].r,u[x].r+1);
        }
    }
    for(auto x:ver){
        for(auto y:chi[x]){
            if(abs(ans[x]-ans[y])!=1){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
    rep(i,0,n-1){
        cout<<ans[i]<<endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 15732
k, n = map(int, input().split())
aList = list(map(int, input().split()))

dList = [0] * n
dMax = 0
for i in range(n-1):
  dList[i] = aList[i+1] - aList[i]
  if dMax < dList[i]:
    dMax = dList[i]

dList[n-1] = aList[0] + k - aList[n-1]
if dMax < dList[n-1]:
  dMax = dList[n-1]

dSum = sum(dList) - dMax
print(dSum)

Measured memory_bytes: 26436
//#include <GOD>

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define si size()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define E end()
#define B begin()
#define pi pair<int, int>
#define en cout << endl
#define cn const
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

cn int maxn = 1e5 + 10;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll dp[maxn][3];

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
		cin >> a[i] >> b[i] >> c[i];
	
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0]; 
	for(int i = 1; i < n; i ++){
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + b[i];
		dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + c[i];
	}
	
	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
	
	return 0;
}



Measured memory_bytes: 4992
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
s = sorted(S())
if s[0] == s[1] and s[1] != s[2] and s[2] == s[3]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3888
#include <bits/stdc++.h> 
#define int long long
#define deb(x) cout<<#x <<" = "<<x<<"\n";
using namespace std; 

signed main() 
{
	string s,t;
  cin>>s>>t;
  int a, b; cin>>a>>b;
  string u; cin>>u;
  if(u == s) a--;
  else b--;
  cout<<a<<" "<<b<<"\n";	
	
	
	
}

Measured memory_bytes: 256
#if __has_include("debug.h")
    #include "debug.h"
#else  
#include <bits/stdc++.h>
using namespace std;
#define d(...) 2;
#endif

#define int long long int

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"      

#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ff first
#define ss second
#define eps 1e-10

#define gcd(a,b)            __gcd((a),(b))
#define lcm(a,b)            ((a*b)/gcd(a,b))

void solve();

int32_t main()
{
    #ifdef DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    #endif 

    fast
    
    int t = 1;
	// cin>>t;
	
	while(t--)
	    solve();
	return 0;  
}

void solve()
{
	int i,j;
	string s,t;
	cin>>s>>t;

	int cnt=0;

	for(i=0;s[i];i++)
	{
		if(s[i]!=t[i])
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;

}

Measured memory_bytes: 3860
from math import gcd
n = int(input())
ab = {}
ans = 0
mod = 10 ** 9 + 7


def go(a, b):
    if a == 0 and b == 0:
        return 0, 0
    elif a == 0:
        return 0, 1
    elif b == 0:
        return 1, 0
    c = gcd(a, b)
    a, b = a // c, b // c
    if a < 0:
        a *= - 1
        b *= - 1
    return a, b


def la(a, b):
    r = max((a, b), go(b, -a))
    if r == (a, b):
        return r, 0
    else:
        return r, 1


zero = 0
for i in range(n):
    a, b = [int(i) for i in input().split()]
    a, b = go(a, b)
    if a == b == 0:
        zero += 1
    else:
        l, ind = la(a, b)
        if l in ab:
            ab[l][ind] += 1
        else:
            ab[l] = [0, 0]
            ab[l][ind] += 1
ans = 1
for i in ab:
    ans *= pow(2, ab[i][0], mod) + pow(2, ab[i][1], mod)-1
    ans %= mod
print((ans + zero-1)%mod)


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

using namespace std;
typedef long long nagai;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i] >> b[i];
	vector<int> lol;
	for (int i = 0; i < n; ++i)
		if (a[i] > b[i])
			lol.push_back(b[i]);
	sort(lol.begin(), lol.end());
	if (lol.size() == 0)
	{
		cout << 0 << '\n';
		return 0;
	}
	nagai ans = 0;
	for (int i = 0; i < n; ++i)
		ans += a[i];
	ans -= lol[0];
	cout << ans << '\n';
}


Measured memory_bytes: 512
s = input()
c = 0
p = 0
l = 1
sl = len(s)
pt = ""
while p + l <= sl:
    t = s[p:p + l]
    if t == pt:
        l += 1
    else:
        c += 1
        p += l
        l = 1
        pt = t
print(c)


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<ll,ll> pii;
const int MD = 1e9+7; typedef vector<ll> VL;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
const int dr[]={0,1,0,-1,0};

int main()
{
 	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int h,w;
	cin >>h >>w;
	vector<VI> ba(h, VI(w, 0));

	rep(i, h) rep(j ,w){ char ch; cin >>ch; ba[i][j] = ch=='#'? 1:0;}
	
	rep(i, h) rep(j, w) if(ba[i][j] ==1){
		rep(k, 4){
			int ni=i+dr[k], nj=j+dr[k+1];
			if(ni<0 || ni>=h || nj<0 || nj>=w) continue;
			if(ba[ni][nj] > 0) ba[ni][nj] = ba[i][j] = 2;
		}
	}
	string ans ="Yes";
	rep(i, h) rep(j, w) if(ba[i][j] ==1) ans="No";
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
/*
小数の桁数を指定する
	cout << setprecision(8)<< mp[0]-mx << endl;
*/

int main()
{
	ll i,j,k,a,b;//,ans=0;
	char c;
	ll N,M,T, X,Y;
	ll tm[100010] = {0};
	cin >> N >> M >>T;
	for(i=0;i<N;++i)
	{
		if(i < M)
			cout << T;
		else
		{
			if(T != 1000000000)
				cout << 1000000000;
			else
				cout << 1;
		}

		if(i < N-1)
			cout << " ";
	}
	cout << endl;
	return 0;
}




















Measured memory_bytes: 1280
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for _ in range(N):
    b = int(input())
    for a in A:
        if b in a:
            a[a.index(b)] = 0

if (any(A[0]) and any(A[1]) and any(A[2])
        and any((A[0][0], A[1][0], A[2][0]))
        and any((A[0][1], A[1][1], A[2][1]))
        and any((A[0][2], A[1][2], A[2][2]))
        and any((A[0][0], A[1][1], A[2][2]))
        and any((A[0][2], A[1][1], A[0][2]))):
    print("No")
else:
    print("Yes")

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

int main()
{
    long long int n,A,B,a=0,b=0;
    cin>>n>>A>>B;
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='a')
        {
            if(a+b<A+B)
                {
                    cout<<"Yes\n";
                    ++a;
                }
            else
                cout<<"No\n";

        }
        else if(s[i]=='b')
        {
            if(a+b<A+B&&b<B)
                {
                    cout<<"Yes\n";
                    ++b;
                }
            else
                cout<<"No\n";
        }
        else
            cout<<"No\n";
    }


    return 0;
}



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

int main() {
  string S;
  string T;
  cin >> S>>T;
  int ans=0;
  int C=S.size();
  for(int i=0;i<C;i++){
    if(S[i]==T[i]){
      ans++;
    }
    else{
      ans*=0;
      break;
    }
  }
  if (ans > 0) {
    cout << "Yes" << endl;
  }
  else{
    cout<<"No"<<endl;
  }

}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int64_t i=0; i<(int64_t)(n); i++)
#define all(v) v.begin(), v.end()

int main(){

    vector<int> x(5);
    rep(i, 5) cin >> x[i];

    rep(i, 5) if(x[i]==0) cout << i+1 << endl;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
int main()
{
	int n, p, s, mx, mn, i, j;
	while (cin >> n, n)
	{
		for (i = 0; i < n; i++)
		{
			for (j = s = 0; j < 5; j++)
			{
				cin >> p;
				s += p;
			}
			if (i == 0) mx = mn = s;
			else
			{
				if (s > mx)
					mx = s;
				if (s < mn)
					mn = s;
			}
		}
		cout << mx << " " << mn << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string a,b;
    cin>>a>>b;
    for(int i=0;i<b.length();i++){
        cout<<a[i]<<b[i];
    }
    if(a.length()>b.length())
        cout<<a[a.length()-1];
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

int main(){
    int N,M;
    cin >> N >> M;
    int num[N],r[N];
    for(int i=0;i<N;i++){
        num[i]=1;
        r[i]=0;
    }
    r[0]=1;
    for(int i=0;i<M;i++){
        int x,y;
        cin >> x >> y;
        x--;y--;
        if(r[x]==1){
            r[y]=1;
        }
        num[x]--;
        num[y]++;
        if(num[x]==0){
            r[x]=0;
        }
    }
    int ans=0;
    for(int i=0;i<N;i++){
        if(r[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

const int N = 100 + 5;

double f(double x, double l, double r, double v) {
    if (x >= 0 && x < l) {
        return v + (l - x);
    }
    else if (x >= l && x < r) {
        return v;
    }
    else {
        return v + (x - r);
    }
}

int main() {
    int i, j, n, time, t[N] = {}, v[N] = {};
    double sum, oldf, newf;

    cin >> n;

    t[0] = 0;
    for (i = 1; i < n + 1; ++i) {
        cin >> time;
        t[i] = t[i-1] + time;
    }

    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }

    sum = 0.0;
    oldf = 0.0;
    for (i = 1; i <= 2 * t[n]; ++i) {
        newf = f(i * 0.5, 0.0, 0.0, 0.0);
        for (j = 0; j < n; ++j) {
            newf = min(newf, f(i * 0.5, (double)t[j], (double)t[j+1], (double)v[j]));
        }
        newf = min(newf, f(i * 0.5, (double)t[n], (double)t[n], 0.0));
        sum += 0.5 * 0.5 * (oldf + newf);
        oldf = newf;
    }

    cout << fixed << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
const int inf = 1 << 30;
const ll linf = 1e18;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

ll N, A, B;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> A >> B;
    ll d = N / (A + B);
    cout << d * A + min(N - d * (A + B), A) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int main()
{
    int x,a,b;
    
    scanf("%d%d%d", &x, &a, &b);
    
    if (-a + b <= 0)printf("delicious\n");
    else if (-a + b <= x)printf("safe\n");
    else printf ("dangerous\n");
    
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    ll ac = 0, bc = 0;
    ll ae, be;
    map<ll, ll> A, B;
    vector<pair<ll, ll>> Av, Bv;
    cin >> N;
    rep(i, N) {
        ll temp;
        cin >> temp;
        if(i % 2) A[temp]++, ac++;
        else B[temp]++, bc++;
    }
    Av = vector<pair<ll, ll>>(A.begin(), A.end());
    Bv = vector<pair<ll, ll>>(B.begin(), B.end());
    Av.push_back({0, 0});
    Bv.push_back({0, 0});
    sort(Av.begin(), Av.end(), [](pair<ll, ll> a, pair<ll, ll> b) { return a.second < b.second; });
    sort(Bv.begin(), Bv.end(), [](pair<ll, ll> a, pair<ll, ll> b) { return a.second < b.second; });
    if(Av.back().first == Bv.back().first) {
        ae = ac - Av[Av.size() - 2].second;
        be = bc - Bv[Bv.size() - 2].second;
        if(ae > be) ae = ac - Av.back().second;
        else be = bc - Bv.back().second;
    } else {
        ae = ac - Av.back().second;
        be = bc - Bv.back().second;
    }
    cout << ae + be << endl;
    return 0;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> P[1<<18];
main(){int H,W,N;cin>>H>>W>>N;for(int i=0;i<N;++i)cin>>P[i].f>>P[i].s;sort(P,P+N);
for(int i=0,c=0;i<N;++i){
if(P[i].s+c<P[i].f){cout<<P[i].f-1;return 0;}
if(P[i].s+c==P[i].f)++c;}
cout<<H;}

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

#define PB push_back
#define SZ(c) int((c).size())
#define ALL(c) (c).begin(), (c).end()
#define CONTAINS(c, x) ((c).find(x) != (c).end())
#define REP(i, n) for(int i=0; i<n; i++)
#define WAIT cout<<flush, system("PAUSE");
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

string s;
int bal, req, sol;

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

	cin >> s;
	for(auto x: s) bal += (x=='g')?1:-1;
	reverse(ALL(s));
	for(auto x: s){
		char c = x;
		if (x == 'g'){
			if (bal >= req+2){
				c = 'p';
				sol ++;
			}
		}
		//cout << sol << endl;
		bal -= (x=='g')?1:-1;
		req += (c=='p')?1:-1;
	}
	
	cout << sol << endl;
}


















Measured memory_bytes: 512
'use strict'

const main = (INPUT) => {
  const input = INPUT.split('\n')[0].split(' ').map(n => Number(n))
  const X = input[2] - input[0]
  const Y = input[3] - input[1]

  console.log(input[2] - Y, input[3] + X, input[0] - Y, input[1] + X)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 7372
import numpy as np
a,b,n= map(int,input().split())

if b-1 <=n:
    value = np.floor(a*(b-1)/b) - a * np.floor((b-1)/b)
else:
    value = np.floor(a*n/b) - a * np.floor(n/b)
print(int(value))

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

int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for(int i = 0;i < N;i++){
    cin >> P[i];
  }
  long long ans = 0;
  int mi = 10000000;
  for(int i = 0;i < N;i++){
    mi = min(mi,P[i]);
    if(mi == P[i]){
      ans++;
    }
  }
  cout << ans << endl;
}

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


int main()
{


        long long n,m,a,b,c,e,f,g,p,q,r,fr,sc,tr,sz,tz,sz1,sz2,i,j,k,mx=-9,mn=999999999999; string str,ttr,ntr;
        long long x=0,y=0,cnt=0,res=0,ttl=0,ans=0,sum=0; long long flg=0,flag=1,na=0,as=1;
        vector<long long>u,v,w; vector< pair<long long,long long> >vct,tct; vector<string>vst;
        set<long long>st,nt,tt; map<long long,long long>mp,nq,qr,mp1,mp2;

        //scanf("%lld",&n);

        cin>>n>>m;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a);  v.push_back(a);
        }
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        for(i=m;i<n;i++)
        {
            res=res+v[i];
        }


        printf("%lld\n",res);








    return 0;
}




Measured memory_bytes: 2420
#include<stdio.h>
#include<stdlib.h>

int main(void) {
  int n, i, count=0, max=0;
  int *h;
  scanf("%d", &n);
  h = (int*)malloc(n*sizeof(int));
  for(i=0; i<n; i++) {
    scanf("%d", &h[i]);
  }
  for(i=0; i<n; i++) {
    if(h[i] >= max) {
      count++;
      max = h[i];
    }
  }
  
  printf("%d\n", count);
  
  return 0;
}


Measured memory_bytes: 128
import numpy as np

N, K = map(int, input().split())
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
for i in range(1, N):
  s = max(0, i-K)
  dp[i] = np.min(dp[s:i] + np.abs(H[i] - H[s:i]))
  
print(dp[-1])


Measured memory_bytes: 22832
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n, k;
    double ans = 0;

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        int res = i;
        double p = 1.0 / n;

        while (res < k)
        {
            res *= 2;
            p /= 2;
        }

        ans += p;
    }

    printf("%.12f\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
struct __test {} test;
using namespace std;
template <typename T>const __test &operator<<(const __test& d,
const T& v) {return cerr << "\033[31m" << v << "\033[0m",d;}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

map<pii,int> m;
const int N = 2e5+5;
int a[N],b[N];

vvi A,B;

bool dfs(int* d, vvi& G, int u, int c) {
	if(d[u]) return 0;
	d[u] = c;
	for(int v : G[u]) {
		dfs(d,G,v,c);
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n,k,l,u,v;
	cin >> n >> k >> l;
	A = vvi(n);
	B = vvi(n);
	while(k--) {
		cin >> u >> v;
		A[--u].pb(--v);
		A[v].pb(u);
	}
	while(l--) {
		cin >> u >> v;
		B[--u].pb(--v);
		B[v].pb(u);
	}
	int _a=1,_b=1;
	for(int i = 0; i < n; ++i) {
		dfs(a,A,i,i+1);
		dfs(b,B,i,i+1);
		++m[pii(a[i],b[i])];
	}
	for(int i = 0; i < n; ++i) {
		cout << m[pii(a[i],b[i])] << "\n";
	}
}

Measured memory_bytes: 27776
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	string s;cin>>s;
	string key = "keyence";
	for(int i=0;i<=7;i++){
		if(s.substr(0,i)+s.substr(s.length()-7+i)==key){
			cout<<"YES";return 0;
		}
	}
	cout<<"NO";
}


Measured memory_bytes: 256
#define w 200001
p;main(n,m,j,i){
  long int k,a[w],A[w],b[w],B[w];
  scanf("%d%d%ld",&n,&m,&k);
  for(i=0;i<n;i++){
    scanf("%ld",&a[i]);
    if(i==0){
      A[i]=0;
    }
    A[i+1]=A[i]+a[i];
  }
    
  for(i=0;i<m;i++){
    scanf("%ld",&b[i]);
    if(i==0){
      B[i]=0;
    }
    B[i+1]=B[i]+b[i];
  }
  int mo=m;
        
  for(i=0;i<=n;i++){
    if(A[i]>k)break;
            
    for(j=mo;j>=0;j--){
      if(A[i]+B[j]<=k){
        if(i+j>p)p=i+j;
        mo=j;
        break;
      }
    }
  }
  printf("%d",p);
}

Measured memory_bytes: 7976
n , k = map(int,input().split())
cnt1 = 0
cnt2 = 0
for i in range(1,n+1):
    if k % 2 == 0 and i % k == 0:
        cnt1 += 1
    elif k % 2 == 0 and i % k == k//2:
        cnt2 += 1
    elif k % 2 == 1 and i % k == 0:
        cnt1 += 1
print(cnt1 ** 3 + cnt2 ** 3)

Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
int ans;
ll dp[1010][1010];
pair<ll, ll> problem[1010];

int main() {
  while (scanf("%d", &n) > 0) {
    MEMSET(dp, 0x01);
    ans = 0;
    REP(i, n) {
      scanf("%lld %lld", &problem[i].second, &problem[i].first);
    }
    sort(problem, problem + n);
    dp[0][0] = 0;
    REP(index, n) {
      FOREQ(solved, 0, index) {
        dp[index + 1][solved] = min(dp[index + 1][solved], dp[index][solved]);
        ll time = dp[index][solved] + problem[index].second;
        if (time <= problem[index].first) {
          ans = max(ans, solved + 1);
          dp[index + 1][solved + 1] = min(dp[index + 1][solved + 1], time);
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 0
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int a = sc.nextInt();
		int b = sc.nextInt();

		if (b % a == 0) {
			pr.println(a + b);
		} else {
			pr.println(b - a);
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


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

int main()
{
  int h,w,K;
  scanf("%d%d%d",&h,&w,&K);
  static char M[810][810];
  for(int i=0;i<h;i++){
    scanf("%s",M[i]);
  }
  static int D[810][810];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      D[i][j]=-1;
    }
  }
  queue<pair<int,int> > Q;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(M[i][j]=='S'){
	D[i][j]=0;
	Q.push(make_pair(i,j));
      }
    }
  }
  int ans;
  while(!Q.empty()){
    int i=Q.front().first,j=Q.front().second;
    Q.pop();
    if(i==0||i==h-1||j==0||j==w-1){
      ans=D[i][j];
      break;
    }
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    for(int v=0;v<4;v++){
      int ni=i+dx[v],nj=j+dy[v];
      if(D[ni][nj]==-1&&(M[ni][nj]=='.'||D[i][j]>=K)){
	D[ni][nj]=D[i][j]+1;
	Q.push(make_pair(ni,nj));
      }
    }
    D[i][j]++;
    Q.push(make_pair(i,j));
  }
  printf("%d\n",(ans+K-1)/K);
  return 0;
}


Measured memory_bytes: 5888
n=int(input())
a=list(map(int,input().split()))

prev=a[0]
state=0 # 0:判断がつかない 1:単調増加 2:単調減少

ans=1

for cur in a:
  #この２パターンのときのみ、区切ることができる。
  if state==1 and prev>cur:
    ans+=1
    state=0
  elif state==2 and prev<cur:
    ans+=1
    state=0
  else:
    if prev>cur:
      state=2
    elif prev<cur:
      state=1
    #5 5など並んでいたもののみを見てもstateは決められない、ゆえに何もしない。
    #前の方でstateが決まっていてそれが続いている
    #または、
    #この時点では分からず後ろを見ていくとわかるの2パターンがあり得る
  prev=cur

print(ans)
#正確に問題を表現。

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define in(e,l) (std::find(l.begin(), l.end(), e) != l.end())
#define asort(l) (std::sort(l.begin(), l.end()))
#define dsort(l) (std::sort(l.rbegin(), l.rend()))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;

int main() {
  ll N, Q;
  cin >> N >> Q;
  vector<pair<ll, ll> > pa(N-1);
  rep(i, N-1){
    cin >> pa[i].first >> pa[i].second;
    --pa[i].first;
    --pa[i].second;
  }
  
  vl p(Q), x(Q);
  rep(i, Q){
    cin >> p[i] >> x[i];
    --p[i];
  }
  
  vl ans(N, 0);
  rep(i, Q){
    ans[p[i]] += x[i];
  }

  asort(pa);

  rep(i, N-1){
    ans[pa[i].second] += ans[pa[i].first];
  }

  rep(i, N) {
    cout << ans[i];
    if(i != N-1){
      cout << " ";
    }
  }
  cout << endl;

  return 0;
}



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

#define all(s) (s).begin(), (s).end()

using namespace std;

bool used[400];
string s;

int find(){
    for(int i = 'a'; i <= 'z'; i++){
        if(!used[i])return i;
    }
    return -1;
}

void next_(int x){
    s[x]++;
    if(s[x] > 'z'){
        s[x] = 'a';
        if(x > 0)next_(x-1);
            else{
                s = "a" + s;
            }
        return;
    }
    return;
}

bool can(int x){
    for(int i = x+1; i <= 'z'; ++i){
        if(!used[i])return true;
    }
    return false;
}

int main() {

    cin >> s;
    bool fucked = false;
    for(int i = 0; i < s.length(); ++i){
        if(used[s[i]])fucked = true;
        used[s[i]] = true;
    }
    
    if(!fucked){
        int it = find();
        if(it != -1){
            s += char(it);
            return cout << s, 0;
        } else {
            fucked = true;
        }
    }
    for(int i = 'a'; i <= 'z'; ++i){
        used[i] = false;
    }
    string c = "";
    int lst = -1;
    for(int i = 0; i < s.length()-1; ++i){
        if(can(s[i])){
            lst = i;
        }
        used[s[i]] = true;
    }
    
    for(int i = 'a'; i <= 'z'; ++i){
        used[i] = false;
    }
    
    if(lst != -1){
        for(int i = 0; i < lst; ++i){
            cout << s[i];
            used[s[i]] = true;
        }
        for(int j = s[lst] + 1; j <= 'z'; ++j){
            if(!used[j]){
                return cout << char(j), 0;
            }
        }
    }
    
    cout << -1;
    
    
    return 0;
}


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

using ll = long long int;

int n, m;
string s;
string t;

map<int, char> mp;

/////////////////////////////////////////////////////////////
int gcd(int m, int n) {
	if ((0 == m) || (0 == n)) return 0;
	while (m != n) {
		if (m > n) m = m - n;
		else n = n - m;
	}
	return m;
}
/////////////////////////////////////////////////////////////

int lcm(int m, int n) {
  if ((0 == m) || (0 == n)) return 0;
  return ((m / gcd(m, n)) * n);
}

int main(void){
  // Here your code !
  scanf("%d %d", &n, &m);
  cin >> s;
  cin >> t;

  if (s[0] != t[0]) {
    printf("%d\n", -1);
    return 0;
  }

  int tmp_gcd = gcd(n, m);

  int ldivn = m / tmp_gcd;
  for (int i = 0; i < n; ++i) {
    mp[i * (ldivn) + 1] = s[i];
  }

  int ldivm = n / tmp_gcd;
  for (int i = 0; i < m; ++i) {
    int cur_ind = i * (ldivm) + 1;
    if (mp.find(cur_ind) != mp.end() && mp[cur_ind] != t[i]) {
      printf("%d\n", -1);
      return 0;
    }
    else {
      mp[cur_ind] = t[i];
    }
  }

  ll l = (ll)tmp_gcd * (ll)ldivm * (ll)ldivn;

  printf("%lld\n", l);

  /*
  for (int i = 1; i <= l; ++i) {
    if (mp.find(i) == mp.end()) printf("%c", 'a');
    else printf("%c", mp[i]);
  }
  printf("\n");

  */


  return 0;
}

Measured memory_bytes: 8192
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,popcnt")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 5050, mod = 1e9 + 7, i2 = (mod+1)/2;
ll n, m, a[5050], b[5050][202], dp[5050][5050], l[5050], r[5050];
vector<int> occ[5050];
void calc(int x) {
	memset(l, 0, sizeof l);
	memset(r, 0, sizeof r);
	//cout << x << " =============== " << x << ":\n";
	for(int i = 1; i <= n; i++) occ[i] = {};
	vector<ll> s = {0};
	b[0][x] = 1<<30;
	b[n+1][x] = 1<<30;
	for(int i = 1; i <= n; i++) {
		while(b[s.back()][x] <= b[i][x]) {
			s.pop_back();
		}
		if(!l[i]) l[i] = s.back();
		s.pb(i);
	}

	s = {n+1};
	for(int i = n; i; i--) {
		while(b[s.back()][x] <= b[i][x]) {
			if(b[s.back()][x] == b[i][x]) {
				//cout << i << " yay " << s.back() << " " << r[s.back()] << '\n';
				if(b[i][x] == b[r[s.back()]][x])
					r[i] = r[s.back()];
				else
					r[i] = s.back();
			}
			s.pop_back();
		}
		if(!r[i]) r[i] = s.back();
		s.pb(i);
	}
	for(int i = 1; i <= n; i++) {
		//cout << i << " " << b[i][x] << " = " << l[i] << " " << r[i] << '\n';
		if(b[i][x] == b[r[i]][x]) {
			occ[r[i]].pb(i);
			continue;
		}
		occ[i].pb(i);
		occ[i].pb(r[i]);
		dp[l[i]+1][r[i]-1] += b[i][x];
		int p = l[i];
		//cout << "Processing " << b[i][x] << " " << l[i] << "; " << r[i] << '\n';
		//for(auto x : occ[i]) cout << x << " "; cout << '\n';
		//cout << l[i]+1 << " " << r[i]-1 << " add\n";
		for(auto xu : occ[i]) {
			//cout << p+1 << " " << xu-1 << " erase\n";
			dp[p+1][xu-1] -= b[i][x];
			p = xu;
		}
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i < n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> b[i][j];
	memset(dp, 0, sizeof dp);
	for(int i = 1; i <= m; i++) calc(i);
	for(int i = 1; i <= n; i++)
		for(int j = n; j >= i; j--) {
			//cout << i << " " << j << " = " << dp[i][j] << " " << dp[i-1][j] << " " << dp[i][j+1] << " " << dp[i-1][j+1] << '\n';
			dp[i][j] += dp[i-1][j] + dp[i][j+1] - dp[i-1][j+1];
			//cout << i << " " << j << " = " << dp[i][j] << '\n';
		}
	ll ans = -(1ll<<60);
	for(int i = 1; i <= n; i++) {
		ll c = 0;
		for(int j = i; j <= n; j++) {
			//cout << i << " " << j << " " << c+dp[i][j]  << '\n';
			ans = max(ans, c+dp[i][j]);
			c -= a[j];
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 207744
#include<cstdio>

int main()
{
    int tate, yoko, mennseki, shu;
    scanf("%d %d", &tate, &yoko);
    mennseki = tate*yoko;
    shu = 2*(tate + yoko);
    printf("%d %d\n", mennseki, shu);
    return 0;
}



Measured memory_bytes: 2616
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int a[1001];
int main(){
    int n;
    while(cin>>n,n){
        rep(i,n) cin>>a[i];
        sort(a,a+n);
        int mn=1000100010;
        FOR(i,1,n){
            mn=min(mn,a[i]-a[i-1]);
        }
        cout<<mn<<endl;
    }
    return 0;
}


Measured memory_bytes: 3184
// Educational DP - ATCoder - B - Frog 2
// A. Bacca
#include <iostream>
#include <vector>
using namespace std;

int n, k;
vector <int> heights;
vector <long long> dp_step;

void Recibir() {
	cin >> n >> k;
	dp_step.assign(n, -1);
	heights.resize(n);
	for (int i=0; i<n; i++) cin >> heights[i];
}

long long Cost(int x) {
	long long c = 10000000000;
	// No saved data
	if (dp_step[x] != -1) return dp_step[x];
	// Last item
	else if (x == n-1) return dp_step[x] = 0;
	else {
		for (int i=1; i<=k; i++) {
			if (x+i > n-1) break;
			else c = min(c, Cost(x+i) + abs(heights[x] - heights[x+i]));
		} 	
		
		return dp_step[x] = c;
	}
}

int main() {
	Recibir();
	cout << Cost(0);
	return 0;
}


Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int ans = 1e9;
    ans = min(ans, x * a + y * b);
    int ab = min(x, y) * 2;
    int rest = x > y ? (x - y) * a : (y - x) * b;
    ans = min(ans, ab * c + rest);
    ab = max(x, y) * 2;
    ans = min(ans, ab * c);
    cout << ans << endl;
    return 0;
}


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

int main(){
  char tp[3];
  for (size_t i = 0; i < 3; i++) {
    cin>>tp[i];
  }
  int num;
  for (size_t j = 0; j < 3; j++) {
    if(tp[j]=='o'){
      num++;
    }
  }
  cout<<700+100*num<<endl;

  return 0;
}


Measured memory_bytes: 256
s = gets.chomp.chars.uniq.sort #要素数を1～4に絞る
if s.size % 2 != 0 #1,3のときはムリ
  puts "No"
elsif s.size == 4 #全部そろっていればok
  puts "Yes"
else
  case s[0]
  when "E"
    if s[1] == "W"
      puts "Yes"
    else
      puts "No"
    end
  when "N"
    if s[1] == "S"
      puts "Yes"
    else
      puts "No"
    end
  else
    puts "No"
  end
end

Measured memory_bytes: 14308