akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize "trapv"
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define ld long double
#define mp make_pair
#define pii pair<int,int>
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,a,n) for(int i=a;i<n;i++)
#define all(v) v.begin(),v.end()
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
int main()
{
    fio;
    int t=1;
    //cin>>t;
    while(t--)
    {
        vector<vector<ll>> vec(1001,vector<ll>(1001,INT_MAX));
        ll dx[]={-1,0,1,0};
        ll dy[]={0,-1,0,1};
        ll n,m;
        cin>>n>>m;
        ll ch,cw;
        cin>>ch>>cw;
        ll dh,dw;
        cin>>dh>>dw;
        char c[n+1][m+1];
        repp(i,1,n+1)
        {
            repp(j,1,m+1)
            {
                cin>>c[i][j];
            }
        }
        deque<pair<ll,ll>> q;
        q.pb({ch,cw});
        vec[ch][cw]=0;
        while(!q.empty())
        {
            ll f=q.front().first;
            ll s=q.front().second;
            ll d=vec[f][s];
            q.pop_front();
            rep(i,4)
            {
                ll ni=dx[i]+f;
                ll nj=dy[i]+s;
                if(ni<=0 || ni>n || nj<=0 || nj>m)
                continue;
                if(c[ni][nj]=='#')
                continue;
                if(vec[ni][nj]<=d)
                continue;
                vec[ni][nj]=d;
                q.push_front({ni,nj});
            }
            repp(i,-2,3)
            {
                repp(j,-2,3)
                {
                    ll bi=f+i;
                    ll bj=s+j;
                    if(bi<=0 || bi>n || bj<=0 || bj>m)
                    continue;
                    if(c[bi][bj]=='#')
                    continue;
                    if(vec[bi][bj]<=d)
                    continue;
                    vec[bi][bj]=d+1;
                    q.pb({bi,bj});
                }
            }
        }
        //cout<<vec[dh-1][dw-1]<<endl;
        cout<<((vec[dh][dw]==INT_MAX)?-1:vec[dh][dw])<<endl;
    }
}

Measured memory_bytes: 17572
from sys import stdin
import math
A, B, C, D, E, F = [int(x) for x in stdin.readline().rstrip().split()]

water = set()
for i in range(0, F//(100*A)+1):
    for j in range(0, F//(100*B)+1):
        water.add(A*i*100+B*j*100)

sugar = set()
capa = math.ceil(F/100)*E
for k in range(0, capa//C+1):
    for l in range(0, capa//D+1):
        sugar.add(C*k+D*l)

W = 0
S = 0
conc = 0
#print(water)
#print(sugar)
for w in water:
    for s in sugar:
        if w + s > F:
            continue
        if w+s == 0:
            continue
        if s > (w / 100)*E:
            continue
        tmp = (100*s)/(w+s)
        if tmp >= conc:
            conc = tmp
            W = w
            S = s
        #print(conc,w,s)
print(W+S,S)


Measured memory_bytes: 40176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//オーバーフローに注意 long long　にする
//'1'+=16;      で大文字Aに
//'大文字'+=32;  で小文字に
//string s = to_string(int数);
//int n = stoi(string文字列);


 
int main() {
 
  int n,t;
  cin >> n >> t;
  
  int ans = 100000;
  
  vector<int> p(n);
  vector<int> q(n);
  rep(i,n) {
  cin >> p[i] >> q[i];
  }
  
  rep(i,n) {
    if(q[i]<=t) {
    ans=min(ans,p[i]);
    }
    
  }
  
  if(ans==100000)puts("TLE");
  else {
  cout << ans << endl;
  }
}

Measured memory_bytes: 384
#B
#差込口: 
#1, a, (a-1)+a, (a-1)+(a-1)+a
from math import ceil
a,b = map(int, input().split())

if b == 1:
    print(0)
elif b < a:
    print(1)
else:
    n = ceil((b-a) / (a-1)) + 1
    print(n)


Measured memory_bytes: 2940
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a == b)cout << "a == b" << endl;
	else if (a > b)cout << "a > b" << endl;
	else cout << "a < b" << endl;
}


Measured memory_bytes: 3012
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;
#define REPP(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,a) for(int i = 0; i < (a); ++i)
#define PER(i,a) for(int i = (a) - 1; i >= 0; --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define MP make_pair

typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int N = 25;
int a[N][N], dp[1 << N];

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

int main() {
    int n;
    cin >> n;
    REP(i, n) REP(j, n) cin >> a[i][j];
    int m = 1 << n, x = 0;
    dp[0] = 1;
    REP(mask, m - 1) {
        x = 0;
        REP(i, n) if (mask & (1 << i)) x++;
        REP(i, n) if (!(mask & (1 << i)) && a[x][i]) {
            add(dp[mask ^ (1 << i)], dp[mask]);
        }
    }
    cout << dp[m - 1] << endl;
    return 0;
}


Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
const int64_t INF =1e18;
int main () {
  
  ll n; cin >> n;
  vector <ll> a(n);
  ll res=1;
  
  for (ll i=0; i<n; i++) {
    cin >> a[i];
  }
  
  for (ll i=0; i<n; i++) {
    if (a[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
    else if (a[i] != 0)
    {
      if (a[i] <= 1000000000000000000/res) res *= a[i];
      else res = -1;
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 4012
import heapq
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.sort()
can = []
p = 0
ans = 0
for i in range(M+1):
    while p<N and (AB[p][0] <= i) :
        heapq.heappush(can,-AB[p][1])
        p += 1
        
    if can != []:
        ans += heapq.heappop(can)
print(-ans)


Measured memory_bytes: 31596
n,h=map(int,input().split())
AB = [list(map(int, input().split())) for i  in range(n)]
AB = sorted(AB, key=lambda x:x[1])
ans = 0

a = sorted(AB)[-1][0]
for i in range(len(AB)):
  if len(AB) <= 0 or h <= 0:
    break
  b = AB.pop(-1)[1]
  h -= b if b > a else a
  ans += 1

if h > 0:
  ans += (h+a-1)//a

print(ans)

Measured memory_bytes: 29680
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

    int N, K;
    cin >> N >> K ;

    vi p(N);
    rep(i, N) cin >> p[i];

    sort(all(p));

    ll sum = 0;
    rep(i, K) sum += p[i];

    cout << sum;

    return 0;
}

Measured memory_bytes: 3656
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/


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

int main()
{
    long n,x,y;
    long index,min = 0;
    
    cin >> n;
    long elevtion[n];
    double elv[n];
    cin >> x >> y;
    for(int p = 0;p < n; ++p)
    {
        cin >> elevtion[p];
    }
    
    for(int p = 0;p < n; ++p)
    {
        elv[p] = x - (elevtion[p] * 0.006);
        
    }
    
    for(int p = 0;p < n; ++p)
    {
        elv[p] = abs (y - elv[p]);
        
    }
    for(int p = 1;p < n; ++p)
    {
        if(elv[p] < elv[min])
        {
            min = p;
            
        }
    }    
        
    cout << min + 1;
    
    return 0;
}


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

vector<int> p, p_sorted;

signed main(){
	int N;
	cin >> N;
	p = p_sorted = vector<int>(N);
	for(int i = 0; i < N; i++){
		cin >> p.at(i);
	}
	p_sorted = p;
	sort(p_sorted.begin(), p_sorted.end());
	int err = 0;
	for(int i = 0; i < N; i++){
		if(p.at(i) != p_sorted.at(i)){
			++err;
		}
	}
	if(err <= 2){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
 
	return 0;
}

Measured memory_bytes: 3652
from fractions import Fraction as F

N = input()
T = map(int, raw_input().split())
V = map(int, raw_input().split())

VL = [V[i] for i in xrange(N)]
VL.append(0)
for i in xrange(N-1, -1, -1):
    VL[i] = min(VL[i], VL[i+1] + T[i])

v1 = F(0)
v2 = F(0)
ans = F(0)

for i in xrange(N):
    t1 = F(0)
    v2 = F(v1)

    while t1 < T[i] and v2 < V[i] and v2 - (T[i] - t1) < VL[i+1]:
        t1 += F(1, 2)
        v2 += F(1, 2)
    v2 = v1 + t1
    ans += (v1 + v2) / F(2) * t1

    t2 = F(0)
    while t1 + t2 < T[i] and v2 - (T[i] - t1 - t2) < VL[i+1]:
        t2 += F(1, 2)
    ans += v2 * t2

    v3 = v2 - (T[i] - t1 - t2)
    ans += (v2 + v3) / F(2) * (T[i] - t1 - t2)

    v1 = v3

print "%.09f" % ans


Measured memory_bytes: 40088
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int H = sc.nextInt();
   int N = sc.nextInt();
   int[] A = new int[N];
   for(int i=0;i<N;i++) A[i] = sc.nextInt();
   int sum = 0;
   boolean yes = false;
   for(int i=0;i<N;i++)
   {
     sum+=A[i];
     if(sum>=H)
     {
       yes = true;
       break;
     }
   }
   String ans = "No";
   if(yes) ans = "Yes";
   System.out.println(ans);
 }
}

Measured memory_bytes: 50960
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) cerr << #x << "=" << static_cast<bitset<16> >(x) << endl;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 10000000;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem2001 : Amida, the City of Miracle **/
int main()
{
	int amida[1010][110];
	int n, m, a, h, p, q;
	while (cin>>n>>m>>a, n||m||a) {
		fill(amida[0], amida[0]+1010*110, 0);
		rep(i, m) {
			cin>>h>>p>>q;
			amida[1001-h][p] = 1;
			amida[1001-h][q] = -1;
		}
		
		rep(i, 1001) {
			a += amida[i][a];
		}
		cout << a << endl;
	}
}

Measured memory_bytes: 1592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x;cin>>x;
    const int NM = 100000;
    bool dp[NM+200];
    rep(i, NM+200) dp[i] = false;
    for(int i=100;i<=105;i++) dp[i] = true;
    for(int i=100; i<=NM; i++) {
        if(dp[i]){
            for(int j=100; j<=105; j++){
                dp[i+j]=true;
            }
        }
    }
    cout<< (dp[x] ? 1:0) <<endl;
}

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

typedef unsigned long long int ull;

int N;

ull targetOfRow[505],targetOfCol[505];
ull opcatOfRow[505],opcatOfCol[505];
ull matrix[505][505];

int zeroCountOfRow[505],zeroCountOfCol[505];

bool check(){
    for(int r=1;r<=N;r++){
        ull androw=-1,orrow=0ull,andcol=androw,orcol=orrow;
        for(int c=1;c<=N;c++){
            androw&=matrix[r][c];
            orrow|=matrix[r][c];
            andcol&=matrix[c][r];
            orcol|=matrix[c][r];
        }

        if (opcatOfRow[r]&&orrow!=targetOfRow[r]) return false;
        if (!opcatOfRow[r]&&androw!=targetOfRow[r]) return false;
        if (opcatOfCol[r]&&orcol!=targetOfCol[r]) return false;
        if (!opcatOfCol[r]&&andcol!=targetOfCol[r]) return false;
    }

    return true;
}

void simpleInference(int pos){
    for(int r=1;r<=N;r++){
        for(int c=1;c<=N;c++){
            //目標値の対応ビットを取り出す
            auto colBit=(targetOfCol[c]>>pos)&1;
            auto rowBit=(targetOfRow[r]>>pos)&1;

            if (colBit^opcatOfCol[c]) matrix[r][c]|=(colBit<<pos);

            if (rowBit^opcatOfRow[r]) matrix[r][c]|=(rowBit<<pos);

            if (rowBit==colBit) matrix[r][c]|=(rowBit<<pos);
        }
    }
}

int main(){

    scanf("%d",&N);

    for(int i=1;i<=N;i++) scanf("%llu",opcatOfRow+i);
    for(int i=1;i<=N;i++) scanf("%llu",opcatOfCol+i);
    for(int i=1;i<=N;i++) scanf("%llu",targetOfRow+i);
    for(int i=1;i<=N;i++) scanf("%llu",targetOfCol+i);

    for(int bit=0;bit<64;bit++){
        ull mask=(ull)1<<(ull)bit;

        simpleInference(bit);

        memset(zeroCountOfCol,0,sizeof(zeroCountOfCol));
        memset(zeroCountOfRow,0,sizeof(zeroCountOfRow));
        for(int r=1;r<=N;r++)
            for(int w=1;w<=N;w++)
                if ((mask&matrix[r][w])==0) zeroCountOfRow[r]++,zeroCountOfCol[w]++;

        for(int r=1;r<=N;r++){
            //今の桁を何にするかを表す
            auto bitTarget=(targetOfRow[r]>>bit)&opcatOfRow[r];
            if (!bitTarget||zeroCountOfRow[r]<N) continue;
            
            int c=1;
            while(c<=N){
                if (opcatOfCol[c]==0&&(targetOfCol[c]&mask)==0&&zeroCountOfCol[c]>1) break;
                c++;
            }
            if (c>N) continue;
            matrix[r][c]|=mask;
            zeroCountOfCol[c]--;
            zeroCountOfRow[r]--;
        }

        for(int c=1;c<=N;c++){
            //今の桁を何にするかを表す
            auto bitTarget=(targetOfCol[c]>>bit)&opcatOfCol[c];
            if (!bitTarget||zeroCountOfCol[c]<N) continue;
            int r=1;
            while(r<=N) { 
                if (opcatOfRow[r]==0&&(targetOfRow[r]&mask)==0&&zeroCountOfRow[r]>1) break;
                r++;
            }
            if (r>N) continue;
            matrix[r][c]|=mask;
            zeroCountOfCol[c]--;
            zeroCountOfRow[r]--;
        }

    }

    if (!check()){
        puts("-1");
        return 0;
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%llu ",matrix[i][j]);
            putchar('\n');
    }

    return 0;
}

Measured memory_bytes: 7444
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
d = LIST()
num = []
for i in range(10):
    if i not in d:
        num.append(i)
ans = inf
for i in range(5):
    for x in product(num,repeat=i+1):
        tmp = 0
        for j in range(i+1):
            tmp += x[j]*10**j
        if tmp >= n:
            ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 10284
#include <iostream>
#include <vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,x;
    cin >> n >> x;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    int ans = 1,d = 0,i = 0;
    while(d+a[i] <= x){
        if(i == n) break;
        ans++;
        d += a[i];
        i++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int arra[n],adit[n];
	for(int i=0;i<n;i++)
	{
		cin>>arra[i]>>adit[i];
	}
	for(int i=0;i<n-2;i++)
	{
	//	cout<<i<<" "<<i+1<<" "<<i+2<<endl;
		if(arra[i]==adit[i] && arra[i+1]==adit[i+1] && arra[i+2]==adit[i+2])
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3612
n,q = map(int,input().split())
v = [[0,0] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    v[p][1] += x
q = [1]
while q:
    now = q.pop()
    v[now][0] = 1
    for i in v[now][2:]:
        if v[i][0] == 0:
            v[i][1] += v[now][1]
            q.append(i)
s = []
for i in v:
    s.append(i[1])
print(*s[1:])

Measured memory_bytes: 58004
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)

int dfs(int idx, int depth, string S, string tmp, int ans)
{
  if (depth == 0)
  {
    int diff = abs(753 - stoi(tmp));
    cout << tmp << endl;
    ans = min(diff, ans);
    return ans;
  }

  rep(idx, S.size())
  {
    if (S.size() - idx == 2 && tmp == "")
      return 1000;
    string x = tmp + S[idx];
    ans = dfs(idx + 1, depth - 1, S, x, ans);
  }

  return ans;
}

int main()
{

  string S;
  cin >> S;
  int ans = 1000;
  string tmp = "";

  rep(i, S.size() - 2)
  {
    string x = tmp + S[i] + S[i + 1] + S[i + 2];
    ans = min(abs(753 - stoi(x)), ans);
  }

  cout << ans;
}

Measured memory_bytes: 256
#ifdef ConanYu
#include "E:\yuzining\code\local.hpp"
#else
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie();
  Main();
  return 0;
}
#endif

void Main() {
  int n, k, c; cin >> n >> k >> c;
  string s; cin >> s;
  if(n == 1) {
    cout << "1\n";
    return;
  }
  vector<int> dp1(n, 0), dp2(n, 0);
  dp1[0] = s[0] == 'o' ? 1 : 0;
  for(int i = 1; i < n; i++) {
    if(s[i] == 'o') {
      if(i - c - 1 >= 0) {
        dp1[i] = max(dp1[i - 1], dp1[i - c - 1] + 1);
      } else {
        dp1[i] = 1;
      }
    } else {
      dp1[i] = dp1[i - 1];
    }
  }
  dp2[n - 1] = s[n - 1] == 'o' ? 1 : 0;
  for(int i = n - 2; i >= 0; i--) {
    if(s[i] == 'o') {
      if(i + c + 1 < n) {
        dp2[i] = max(dp2[i + 1], dp2[i + c + 1] + 1);
      } else {
        dp2[i] = 1;
      }
    } else {
      dp2[i] = dp2[i + 1];
    }
  }
  if(dp2[1] < k) cout << 1 << '\n';
  for(int i = 1; i < n - 1; i++) {
    if(dp1[i - 1] + dp2[i + 1] < k) {
      cout << (i + 1) << '\n';
    }
  }
  if(dp1[n - 2] < k) cout << n << '\n';
}

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

#define rep(i,n) for(int i = 0;i < n;++i)
#define rep2(i,n,m) for(int i = n;i < m;++i)
#define all(v) v.begin(),v.end()

using namespace std;
using ll = long long;
const int INF = 1001001001;


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

    ll n;
    bool f = false;
    string s;
    char v;
    deque<char> q;

    cin >> s >> n;
    for(char c : s) q.push_back(c);

    rep(i,n){
        int a;
        cin >> a;
        if(a == 1){
            f = !f;
        }else{
            int b;
            cin >> b >> v;
            if(b == 1){
                if(f) q.push_back(v);
                else q.push_front(v);
            }else{
                if(f) q.push_front(v);
                else q.push_back(v);
            }

        }
    }

    if(f){
        for(int i = q.size()-1;i >= 0;--i){
            cout << q.at(i);
        }
    }else{
        rep(i,q.size()) cout << q.at(i);
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 976
x1, y1, x2, y2 = gets.chomp.split.map(&:to_i)
x, y = [x1, x2], [y1, y2]

puts (0..1).map {|i| 
    x[i+2], y[i+2] = y[i] - y[i+1] + x[i+1], x[i+1] - x[i] + y[i+1]
    [x[i+2], y[i+2]].join(" ")
}.join(" ")

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 +7;
const lli inf = 1e18;
typedef pair<lli, lli> pll;

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
    return 0;
}

Measured memory_bytes: 256
public class Main {
    public static void main(String[] args) {

        java.util.Scanner sc = new java.util.Scanner(System.in);

        int n = sc.nextInt(); // number of places
        int[] a = new int[n + 2];

        {
            int i = 0;
            a[i] = 0; // starting point
            for (i = 1; i <= n; ++i) {
                a[i] = sc.nextInt(); // place location
            }
            a[i] = 0; // To make calculations easier
        }

        long full = 0;
        for (int i = 0; i < n + 1; ++i) {
            full += Math.abs(a[i + 1] - a[i]);
        }

        for (int i = 1; i < n + 1; ++i) {
            long  distance = full;
            int s = a[i];
            int s0 = a[i - 1];
            int s1 = a[i + 1];
            if (!(s0 <= s && s <= s1)) {
                // If skip place is not in between previous and next
                // skipping will affect entire distance so recalculate affected part
                distance += (-Math.abs(s1 - s) - Math.abs(s - s0) + Math.abs(s1 - s0));
            }
            System.out.println(distance);
        }
    }
}


Measured memory_bytes: 62756
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int N = sc.nextInt();
		int aFrom = sc.nextInt();
		int bFrom = sc.nextInt();
		int aTo = aFrom;
		int bTo = bFrom;
		char[] S = sc.next().toCharArray(), T = sc.next().toCharArray();
		boolean wins = false;
		for (int i = 0; i < N && !wins; i++) {
			if (S[i] == 'U') {
				aFrom--;
				if (aFrom < 1) wins = true;
			} else if (S[i] == 'D') {
				aTo++;
				if (aTo > H) wins = true;
			}
			if (T[i] == 'U') {
				aTo = Math.max(1, aTo - 1);
			} else if (T[i] == 'D') {
				aFrom = Math.min(H, aFrom + 1);
			}
			if (S[i] == 'L') {
				bFrom--;
				if (bFrom < 1) wins = true;
			} else if (S[i] == 'R') {
				bTo++;
				if (bTo > W) wins = true;
			}
			if (T[i] == 'L') {
				bTo = Math.max(1, bTo - 1);
			} else if (T[i] == 'R') {
				bFrom = Math.min(W, bFrom + 1);
			}
		}
		out.println(wins ? "NO" : "YES");
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 26992
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <cctype>

using namespace std;

int main() {
 
	//数字
   long long int N;
   long long int A;
   long long int B;
   long long int max;
   long long int min;

   cin >> N >> A >> B;
   
   if((B-A)%2==0){
      printf("%lld\n",(B-A)/2);
   }else{
      //差が奇数
      max = N-B;
      min = A-1;
      printf("%lld\n",(B-A-1)/2+(max<min?max:min)+1);
   } 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll K;
    cin >>K;
    vector<ll>a(50);

    rep(i,50){
        a[i]+=50-i-1 + K/50;
    }
    ll m=K%50;

    rep(i,m){
        a[i]++;
    }
    
    cout << 50 << endl;
    rep(i,50){
        cout<<a[i]<<" ";
    }
    cout<<endl;


    return 0;
    

}

Measured memory_bytes: 3656
from subprocess import*
call(('python3','-c',"""
import numpy as np
bisect_left = np.searchsorted
input()
a = np.int32(input().split())
b = np.int32(input().split())
ans = 0
for k in range(28, -1, -1):
    low = pow(2, k)
    high = pow(2, k + 1)
    a %= high
    b %= high
    b.sort()
    y = np.hstack((b - high, b))
    left = bisect_left(y, low - a)
    right = bisect_left(y, high - a)
    if np.sum(right - left) % 2:
        ans += low
print(ans)
"""))

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

int main() {
  bool p[60001];
  int n, x;

  memset(p, 0, sizeof(bool)*60001);
  for (int i=2; i*i<=60000; i++) {
    if (!p[i]) {
      for (int j=2*i; j<=60000; j+=i) {
        p[j] = true;
      }
    }
  }
  while (scanf("%d", &n) == 1) {
    x = n-1;
    while (p[x]) --x;
    printf("%d ", x);
    x = n+1;
    while (p[x]) ++x;
    printf("%d\n", x);
  }
  return 0;
}

Measured memory_bytes: 1088
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn=100003;
 
int n,a[maxn],o[maxn];
ll f[maxn][3];
char s[3];
 
int main(){
	scanf("%d",&n);
	scanf("%d",&a[1]);
	for(int i=2;i<=n;++i){
		scanf("%s%d",s,&a[i]);
		if(s[0]=='-')o[i]=1;
	}
	for(int i=0;i<=n;++i)
		for(int j=0;j<3;++j)
			f[i][j]=-1e18;
	f[0][0]=0;
	for(int i=1;i<=n;++i){
		if(!o[i]){
			f[i][0]=max(f[i-1][0]+a[i],f[i-1][1]+a[i]);
			f[i][1]=max(f[i-1][1]-a[i],f[i-1][2]+a[i]);
			f[i][2]=f[i-1][2]+a[i];
		}else{
			f[i][1]=max(f[i-1][0]-a[i],f[i-1][1]+a[i]);
			f[i][2]=max(f[i-1][2]+a[i],f[i-1][1]+a[i]);
		}
		
	}
	printf("%lld\n",max(f[n][0],f[n][1]));
	return 0;
}
 

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

/**
 * Made by egor https://github.com/chermehdi/egor.
 * 
 * @author Azuz
 * 
 */
public class Main {

    void solve(Scanner in, PrintWriter out) {
      out.println(in.nextInt() ^ 1);
    }

    public static void main(String[] args) {
        try(Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)) {
            new Main().solve(in, out);
        }
    }
}


Measured memory_bytes: 35980
#include <bits/stdc++.h>
const int INF = 1e9;
#define int long long
using namespace std;

int dig_max(int a, int b){
    string sa = to_string(a);
    string sb = to_string(b);
    return max(sa.size(), sb.size());
}

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

    int ans = INF;
    for(int i = 1; i*i <= n; i++){
        if(n % i == 0){
            ans = min(ans, dig_max(i, n/i));
        }
    }
    cout << ans << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 2005
using namespace std;

int n, k, q, s, e, mn = 1e9, a[N];
vector<int> va, vt;

void f(int p, int q) {
	int i;
	vt.clear();
	if (q - p + 1 < k) return;
	for (i = p; i <= q; i++) vt.push_back(a[i]);
	sort(vt.begin(), vt.end());
	for (i = 0; i <= vt.size() - k; i++) va.push_back(vt[i]);
}

int main()
{
	int i;
	cin >> n >> k >> q;
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	for (i = 0; i < n; i++) {
		va.clear();
		for (s = 0; s < n; s = e + 1) {
			for (e = s; e <= n && a[e] >= a[i]; e++);
			f(s, e - 1);
		}
		sort(va.begin(), va.end());
		if (va.size() >= q) mn = min(mn, va[q - 1] - va[0]);
	}
    cout << mn << endl;
    return 0;
}

Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <sstream>
#include <numeric>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define np(v) next_permutation(v.begin(), v.end())
#define pll pair < long long, long long>
#define all(a) a.begin(), a.end()
#define ull unsigned long long
#define pii pair < int, int >
#define sz(a) (int)a.size()
#define sqr(x) ((x) * (x))
#define y1 stupid_cmath
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second

const int inf = (int)3e6;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);

int a,b,c,d;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> a >> b >> c >> d;
    if(a <= c && d <= b) return cout << (d - c) << endl, 0;
    if(c > b || d < a) return cout << 0 << endl, 0;
    if(c <= a && b <= d) return cout << (b - a) << endl, 0;
    if(a <= c && c <= b) return cout << b - c << endl, 0;
    if(a <= d && d <= b) return cout << d - a << endl, 0;
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
red = [False] * n
red[0] = True
box = [1] * n
for i in range(m):
    x,y = map(lambda x:int(x)-1, input().split())
    box[x] -= 1
    box[y] += 1
    if red[x]:
        red[y] = True
    if box[x] == 0:
        red[x] = False
cnt = 0
for i in range(n):
    if red[i]:
        cnt += 1
print(cnt)


Measured memory_bytes: 11644
#include <cstdio>
#include <map>

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

using namespace std;

int main(){
	int n; scanf("%d",&n);
	map<int,int> f;
	rep(i,n){ int a; scanf("%d",&a); ++f[a]; }

	int ans=0;
	for(auto x:f){
		if     (x.first<x.second) ans+=x.second-x.first;
		else if(x.first>x.second) ans+=x.second;
	}
	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int n,k,ans;
  cin>>n>>k;
  int h[n+1];
  for(int i=1;i<=n;i++)
  {
cin>>h[i];}
  long int dp[n+1]={0};
  dp[2]=abs(h[2]-h[1]);
 for(int i=3;i<=n;i++)
 {ans=dp[i-1]+abs(h[i]-h[i-1]);
   for(int j=1;j<=k;j++)
   {if(i-j>=1)
   {ans=min(dp[i-j]+abs(h[i]-h[i-j]),ans);
    dp[i]=ans;
   }
   }
 }
		
  cout<<dp[n];
  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

void cout_vec(vector<long long> &vec){
    for(int i=0; i<vec.size(); i++){
        if (i!=0){
            cout << ' ';
        }
        cout << vec[i];
    }
    cout << endl;
}

void cout_mat(vector<vector<long long>> &mat){
    for(int i=0; i<mat.size(); i++){
        vector<long long> vec = mat[i];
        cout_vec(mat[i]);
    }
}

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

    vector<vector<long long> > dp(N+1,vector<long long>(N+1,0));
    for(int i=1; i<=N; i++){
        for(int j=0; j < N-i+1; j++){
            dp[j][j+i]=max((long long) a[j]-dp[j+1][j+i], (long long) a[j+i-1]-dp[j][j+i-1]);
        }
    }

    //cout_mat(dp);
    cout << dp[0][N] << endl;
}

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

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

#define MOD 1000000007LL

#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;
    cin >> N;
    string S;
    cin >> S;
    ll ans = 0;
    rep(i, N - 2) {
        if(S.substr(i, 3) == "ABC") ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define X first
#define Y second
#define pie 3.14159265358979323846
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;


template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int mod =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

ll RS(ll N,ll P,ll M){
    if(P==0){
        return 1;
    }else{
        if(P%2==0){
            ll t=RS(N,P/2,M);
            return t*t%M;
        }else{
            return N*RS(N,P-1,M)%M;
        }
    }
}
bool greater_pair(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first!=b.first){
        return a.first>b.first;
    }else{
        return a.second>b.second;
    }
}
int main() {
    ios::sync_with_stdio(false);
    int N=in();
    int ans=0;
    int min_d=101;
    REP(i,N){
        int a=in();
        ans+=a;
        if(a%10>0){
            chmin(min_d,a);
        }
    }
    
    if(ans%10==0){
        if(min_d<101){
            ans-=min_d;
        }else{
            ans=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

class UnionFind{
private:
	vector<int> par; //�e
	vector<int> sz; //�f�[�^�̐�

public:
	UnionFind(int n){ 
		par = vector<int>(n);
		sz = vector<int>(n);
		for(int i = 0; i < n; i++){
			par[i] = i;
			sz[i] = 1;
		}
	}
	//�؂̍������߂�
	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	//x��y�̑�����W���𕹍�
	void unite(int x,int y){
		x = find(x); //x,y�͊e�f�[�^�̍��m�[�h�𓾂�
		y = find(y);
		if(x == y) return;
		if (sz[x] < sz[y]) swap(x,y);
		par[y] = x; //x��y�̐e�ƂȂ�悤�ɘA������
		sz[x] += sz[y];
	}
	//x��y�������W���ɑ����邩�ۂ�
	bool same(int x, int y){
		return find(x) == find(y);
	}
	//x��������W���̃f�[�^��
	int size(int x){
		return sz[find(x)];
	}
};

int main()
{
	int n,m;
	cin >> n >> m;
	vi p(n),x(m),y(m);
	UnionFind uni(100010);
	rep(i,n) cin >> p[i];
	rep(i,m){
		cin >> x[i] >> y[i];
		uni.unite(x[i],y[i]);
	}
	int ans = 0;
	rep(i,n){
		if(uni.same(p[i],i+1)) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

using ll = long long;

#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int res = 0;
    REP(i, 0, n) {
    	int x;
    	cin >> x;
    	res += (x%2 && (i+1)%2);
    }
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, ans;
  cin >> a >> b;
  if(a >= b)
  {
  	ans += a;
    a--;
  }
  else
  {
    ans += b;
    b--;
  }
  if(a >= b)
  {
  	ans += a;
  }
  else
  {
    ans += b;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp

#define NIL -1

struct Node
{
    int l, r, p;
};

int n;
Node T[100005];

static void preOrder(int i) {
    if (i == NIL) return;
    printf(" %d", i);
    preOrder(T[i].l);
    preOrder(T[i].r);
}

static void inOrder(int i) {
    if (i == NIL) return;
    inOrder(T[i].l);
    printf(" %d", i);
    inOrder(T[i].r);
}

static void postOrder(int i) {
    if (i == NIL) return;
    postOrder(T[i].l);
    postOrder(T[i].r);
    printf(" %d", i);
}

int main() {
    cin >> n;
    REP(i, n) T[i].p = NIL;

    REP(i, n) {
        int id, l, r;
        cin >> id >> l >> r;
        T[id].l = l;
        T[id].r = r;
        if (l != NIL) T[l].p = id;
        if (r != NIL) T[r].p = id;
    }


    int root = 0;
    REP(i, n) if (T[i].p == NIL) root = i;

    cout << "Preorder" << "\n";
    preOrder(root); cout << "\n";
    cout << "Inorder" << "\n";
    inOrder(root); cout << "\n";
    cout << "Postorder" << "\n";
    postOrder(root); cout << "\n";
    return 0;
}



Measured memory_bytes: 3212
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    H, W = MI()
    room = [["" for j in range(W)] for i in range(H)]
    roomT = [["" for i in range(H)] for j in range(W)]
    num_yoko = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        row = input()

        splited = list(map(len, row.split('#')))
        tmp = 0
        for j in range(W):
            roomT[j][i] = row[j]
            room[i][j] = row[j]
            if row[j] == "#":
                num_yoko[i][j] = 0
                tmp += 1
            else:
                num_yoko[i][j] = splited[tmp]

    ans = 0

    for j in range(W):
        target = roomT[j]
        splited = list(map(len, "".join(target).split('#')))
        tmp = 0
        for i in range(H):
            num_tate = 0 if target[i] == "#" else splited[tmp]
            ans = max(ans,  num_tate + num_yoko[i][j] - 1)
            if target[i] == "#":
                tmp += 1
    print(ans)


main()


Measured memory_bytes: 430120
#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;

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

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

int main() {
  ll N;
  cin>>N;
  vector<vector<ll>> v(N,vector<ll>(3));
  for(ll i = 0LL; i < N; i++) {
    cin>>v[i][0]>>v[i][1]>>v[i][2];
  }
  pair<ll,ll> cen;
  ll H=0LL;
  for(ll i = 0LL; i <= 100LL; i++) {
    for(ll j = 0LL; j <= 100LL; j++) {
      bool ok = true;
      vector<ll> hi;
      for(auto x:v){
        hi.push_back(abs(x[0]-i)+abs(x[1]-j));
      }
      vector<ll> hiest;
      for(ll k = 0LL; k < N; k++) {
        if(v[k][2]==0LL)continue;
        hiest.push_back(hi[k]+v[k][2]);
      }
      ll t = hiest[0];
      for(ll x:hiest){
        if(t!=x) ok=false;
      }
      if(ok){
        bool ook=true;
        for(auto x:v){
          if(x[2]!=max(t-abs(x[0]-i)-abs(x[1]-j),0LL))ook=false;
        }
        if(ook){
          cen.first=i;
          cen.second=j;
          H=t;
        }
      }
    }
  }
  cout<<cen.first<<" "<<cen.second<<" "<<H<<endl;
}

Measured memory_bytes: 256
#動的計画法
#D - Knapsack 1
#インデックスの順番でなく重さを基準に動的計画していく
N, W = list(map(int,input().split()))
item = [list(map(int,input().split())) for i in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    #print(w,v)
    for j in range(W-w,-1,-1):
        if dp[j] != -1:
            if dp[j] + v > dp[j+w]:
                dp[j+w] = dp[j] + v
        #print(dp)
print(max(dp))

Measured memory_bytes: 41452
#include <stdio.h>
#include <string.h>
char s1[105],s2[105];
int main()
{   
	int i,j,l1,l2,flag,g;
	scanf("%s%s",s1,s2);
	l1=strlen(s1);
	l2=strlen(s2);
	for(j=0;j<l1;j++)
	     {g=s1[0];flag=0;
	      for(i=0;i<l1-1;i++)
	         s1[i]=s1[i+1];
	      s1[l1-1]=g;
	      for(i=0;i<l1;i++)
		  if(s1[i]==s2[i])
		      flag++;
	      if(flag==l1)break;  
	 }
	if(flag==l1)
	      printf("Yes\n");
	else 
	      printf("No\n");
	
}

Measured memory_bytes: 128
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include <string.h>
#include <math.h>

int main(void) {
	uint32_t A, B, K;

	scanf("%"PRIu32" %"PRIu32" %"PRIu32, &A, &B, &K);

	if ((B - A + 1) <= K * 2) {
		for (uint32_t num = A; num < B; num++) {
			printf("%"PRIu32"\n", num);
		}
		printf("%"PRIu32, B);
	}
	else {
		for (uint32_t num = A; num < A + K; num++) {
			printf("%"PRIu32"\n", num);
		}
		for (uint32_t num = B - K + 1; num < B; num++) {
			printf("%"PRIu32"\n", num);
		}
		printf("%"PRIu32, B);
	}

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    lint bb = min({a, b, c, d, e});
    lint cc = (n + bb - 1) / bb;
    cout << cc + 4 << "\n";
    return 0;
}

Measured memory_bytes: 256