akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

using namespace std;

int main(){
    char str[20001];
    int m,tmp,length;
    while(true){
        scanf("%s",str);
        if(str[0]=='-') break;
        length=0;
        for(int k=0; str[k] != '\0'; k++) length++;
        scanf("%d",&m);
        int index=0;
        for(int i=0; i<m; i++){
            scanf("%d",&tmp);
            for(int j=0; j<tmp; j++){
                str[index+length]=str[index];
                index++;
            }
        }
        for(int p=0; p<length; p++){
            printf("%c",str[index+p]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2696
n,k=map(int,input().split())
sunuke=[0]*n
ans=0
for i in range(k):
    d=int(input())
    a=list(map(int,input().split()))
    for j in range(d):
        if sunuke[a[j]-1]==0:
            sunuke[a[j]-1]=1
for i in range(n):
    if sunuke[i]==0:
        ans+=1
print(ans)

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>

using namespace std;
using namespace __gnu_pbds; 

typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    policy_set;  

#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define ALL(c) c.begin(),c.end()
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

void preprocess(){


}
const ll N=3e5+7;
const ll INF=1e18+1;
const ll MOD=1e9+7;
//Have to ramp up more on implementation skillz to do it fast,
// and debug skillz, it is not as easy as you think with two pointers
ll n,a[N],pref[N],ans,pref_xor[N];
ll ok_lb(ll l1,ll r1){
   return (pref[r1]-pref[l1-1])<=(pref_xor[r1]^pref_xor[l1-1]);
}
ll ok_ub(ll l1,ll r1){
    // cout<<(pref_xor[r1]^pref_xor[l1-1])<<"\n";
    return (pref[r1]-pref[l1-1])<(pref_xor[r1]^pref_xor[l1-1]);
}
//THis is just a shift of binary search applied to this
// Today you shall revise two pointers as well good.
// two observations if for a set or ==sum then for any subset that is true
// this again warrants two pointers approahc only, but can be done also by bs
void find_left(ll i){
    ll start=1,end=i-1;
    while(start<=end){
        ll mid=(start+end)/2;
        if(ok_lb(mid,i))
            end=mid-1;
        else
            start=mid+1;
    }
    ll start1=1,end1=i-1;
    while(start1<=end1){
        ll mid=(start1+end1)/2;
        // cout<<start1<<" "<<end1<<"\n";
        if(ok_ub(mid,i))
            end1=mid-1;
        else
            start1=mid+1;
    }
    // cout<<start1<<" "<<start<<"\n";
    ans+=start1-start;
}

void solve(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
        pref_xor[i]=pref_xor[i-1]^a[i];
    }
    for(ll i=1;i<=n;i++){
        find_left(i);
    }
    // cout<<ok_ub(2,2)<<"\n";
    cout<<n+ans<<"\n";
}
int main() {
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	preprocess();
	int t=1;
	//cin>>t;
	//cout<<t<<endl;
	for(int i=0;i<t;i++)
		solve();
	return 0;
}



Measured memory_bytes: 6016
// #pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define String std::string
#define fir first
#define sec second
#define mp std::make_pair
#define Pair std::pair<int, int>
#define Map std::map< int, int >
#define Vector std::vector<int>

typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
const int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };
const int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

inline int read() {
    int res = 0;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar());
    for (; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + ch - '0';
    return res;
}

int n;
int a[N], f[N];
std::vector<int> ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = n; i >= 1; i--) {
        int tmp = 0;
        for (int j = i; j <= n; j += i) {
            tmp += f[j];
        }
        if (tmp % 2 != a[i]) {
            f[i] = 1;
            ans.push_back(i);
        }
    }
    printf("%d\n", (int)ans.size());
    for (int i = ans.size() - 1; i >= 0; i--) printf("%d\n", ans[i]);
    return 0;
}

Measured memory_bytes: 2936
# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import collections
#import math

def main():
    for x in sys.stdin:
        x = x.strip("\n")
        ans = set()
        try:
            int(x)
            continue
        except:
            for i in range(1,len(x)):
                f, e = x[:i], x[i:]
                fr = f[::-1]
                er = e[::-1]
                ans = ans.union(set([x, f+er, fr+e, fr+er, e+f,er+f, e+fr, er+fr]))
            print(len(ans))


if __name__ == '__main__':
    main()



Measured memory_bytes: 5644
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm> 
#include<stack>
using namespace std;
stack<char>s;
string k;
int main(){
    cin>>k;
    int lk=k.length();
    for(int i=0;i<lk;i++)
    {
        s.push(k[i]);
    }
    bool flag=1;
    for(int i=0;i<lk;i++)
    {
        char top=s.top();
        if(top=='b') top='d';
        else if(top=='d') top='b';
        else if(top=='p') top='q';
        else if(top=='q') top='p';
        if(top==k[i])
         {
            flag=1;
            s.pop();
        }
        else 
        {
            flag=0;
            break;
        }
    }
    if(flag==0) printf("No");
    else printf("Yes");
    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n, k;
    cin >> n >> k;
    int ans = k;
    rep(i, n - 1) ans *= k - 1;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FOR(i, n) for(int i = 0; i < (n); i ++)
#define CIN(type, val) type val; cin >> val;
#define COUT(val) cout << (val) << "\n";
using namespace std;
using ll = long long;

int num_digit(ll k){
    int d = 1;
    while(k > 1) k /= 2, d ++;
    return d;
}

int n;
ll a[100001], ds[100];

ll dp(int d, ll k){
    if(d < 0) return 0;
    if((1ll << (d+1)) - 1ll <= k){
        ll sum = 0;
        FOR(e, d+1) if(ds[e] > 0) sum += ds[e];
        return sum;
    }
    if((1ll << d) > k) return dp(d-1, k);
    return max(dp(d-1, k), ds[d] + dp(d-1, k - (1ll << d)));
}

int main(void){
    ll k;
    cin >> n >> k;
    FOR(i, n) cin >> a[i];
    int dk = num_digit(k);
    
    FOR(d, dk){
        FOR(i, n) ds[d] += (((a[i] & (1ll << d)) ? -1ll : 1ll) * (1ll << d));
        // COUT(ds[d]);
    }
    
    ll ans = dp(dk-1, k);
    FOR(i, n) ans += a[i];
    
    COUT(ans);
}

Measured memory_bytes: 1024
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}



int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r;

      bool flag=false;

      string str;

      cin>>a>>b;

        for(i=0; i<=a; i++)
        {
            sum=(i*4)+(a-i)*2;

            if(sum==b)
            {
                cout<<"Yes"<<endl;

                return 0;
            }
        }

        cout<<"No"<<endl;
}



Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        
        int socket = 1;
        int count = 0;
        while(socket < b){
            socket += a-1;
            count++;
        }
        
        System.out.println(count);
    }
}

Measured memory_bytes: 22612
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define il inline
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define rep0(i, n) for(int i = 0; i < (n); i ++)
#define per0(i, n) for(int i = (n) - 1; i >= 0; i --)
#define ept 1e-9
#define INF 0x3f3f3f3f
#define sz(x) (x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int l[200010], r[200010];
ll ans;
int main()
{
	int n = read();
	rep(i, 1, n)
	{
		int L = read();
		int R = read();
		L += 1e5;
		R += 1e5;
		r[R] ++;
		l[L] ++;	
	}
	rrep(i, 2e5, 0) l[i] += l[i + 1];
	rep(i, 1, 2e5) r[i] += r[i - 1];
	rep(i, 1, 1e5) ans += min(r[i - 1], l[i] + 1);
	rep(i, 1e5 + 1, 2e5) ans += min(r[i - 1] + 1, l[i]);
	cout << ans * 2;
}


Measured memory_bytes: 1920
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int S = sc.nextInt();
    int W = sc.nextInt();
    if(S<=W){
      System.out.println("unsafe");
    }else{
      System.out.println("safe");
    }
  }
}

Measured memory_bytes: 35604
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final long A = sc.nextLong();
			final long B = sc.nextLong();
			
			for(long i = 0; i <= B * 110; i++) {
				final long i_a = (i * 108) / 100 - i;
				final long i_b = (i * 110) / 100 - i;
				
				if(i_a == A && i_b == B) {
					System.out.println(i);
					return;
				}
			}
			
			System.out.println(-1);
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 24660
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1e+7
#define MOD 1000000007
using namespace std;



int main(){
    string S;
    cin>>S;
    int ans=100000;
    for(int i=0; i<=S.length()-3; i++){
        int temp=(S[i]-'0')*100+(S[i+1]-'0')*10+(S[i+2]-'0');
        ans=min(ans, abs(temp-753));
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool prime(int n){
  for(int i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return true;
}
int main(){
  int n;cin>>n;
  int cnt=0;
  for(int i=3;;i+=10){
    if(prime(i)){
      cnt++;
      cout<<i<<endl;
    }
    if(cnt==n)break;
  }
}

Measured memory_bytes: 256
import fractions

N,X=map(int,input().split())
x=list(map(int,input().split()))+[X]
x.sort()
#print(x)

y=[]
for i in range(N):
  y.append(x[i+1]-x[i])
#print(y)

max_gcd=y[0]
for i in range(N):
  max_gcd=fractions.gcd(max_gcd,y[i])
print(max_gcd)

Measured memory_bytes: 16300
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace AtC
{
    class Program
    {
        static void Main(string[] args)
        {
            var rgbn = ReadIntArray();
            int R = rgbn[0], G = rgbn[1], B = rgbn[2], N = rgbn[3];
            int count = 0;
            for (int r = 0; r * R <= N; r++)
            {
                for (int g = 0; r * R + g * G <= N; g++)
                {
                    if ((N - (r * R + g * G)) % B == 0) count++;
                }
            }

            Out(count);
        }

        //最小公倍数
        static int LCM(int num1, int num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        static long LCM(long num1, long num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        //最大公約数
        static int GCD(int num1, int num2)
        {
            int a = Math.Max(num1, num2);
            int b = Math.Min(num1, num2);
            int mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static long GCD(long num1, long num2)
        {
            long a = Math.Max(num1, num2);
            long b = Math.Min(num1, num2);
            long mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        static long[] ReadLongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }

        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }

        static string ReadString()
        {
            return Console.ReadLine();
        }

        static void Out(object o)
        {
            Console.WriteLine(o);
        }
    }

    static class EnumerableExtension
    {
        public delegate void Function<in T>(T val);

        public static void ForEach<T>(this IEnumerable<T> enumerable, Function<T> function)
        {
            foreach (var x in enumerable)
            {
                function(x);
            }
        }
    }

    class PriorityQueue<T>
    {
    }
}

Measured memory_bytes: 13396
n = int(input())
S = list(input())
input()
MOD = 10**9+7

x = []
p = S[0]
c = 1
for s in S[1:]:
    if s == p:
        c += 1
    else:
        x.append(c)
        c = 1
    p = s
x.append(c)

ans = x[0]*3
for i in range(1, len(x)):
    if x[i-1] == 1:
        ans = (2*ans) %MOD
    else:
        if x[i] == 1:
            pass
        else:
            ans = (3*ans) %MOD
print(ans)


Measured memory_bytes: 3064
s = input()

index_a = 0
index_z = 0

for i, a in enumerate(s):
    if a == 'A':
        index_a = i
        break

length = len(s)
for i, a in enumerate(reversed(s)):
    if a == 'Z':
        index_z = length - 1 - i
        break

print(index_z - index_a + 1)


Measured memory_bytes: 3516
#include <iostream>
using namespace std;
int Solve(int n) {
    if(n == 0) return true;
    if(n < 0) return false;
    return Solve(n - 4) || Solve(n - 7);
}

int main() {
    int n,res;

    cin >> n;

    if(Solve(n)==1){
    cout << "Yes" << endl;
    }
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	//4方向の場合は0～5,8方向は0～9でループ
	static int[] around = { -1, 0, 1, 0, -1, 1, 1, -1, -1 };

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();

		int HI = Integer.parseInt(W.split(" ")[0])+2;
		int WI = Integer.parseInt(W.split(" ")[1])+2;

		boolean[][] S = new boolean[HI][WI] ;
		for(int i=0;i<S.length;i++){
			Arrays.fill(S[i], false);
		}
		for(int i=0;i<S.length-2;i++){
			W = in.readLine();
			for(int k=0;k<W.length();k++){
				if('.' == W.charAt(k)){
					S[i+1][k+1] = true;
				}else{
					S[i+1][k+1] = false;
				}
			}
		}
		int ans = -1;
		for(int w=0;w<S.length;w++){
			for(int h=0;h<S[0].length;h++){
				if(!S[w][h]){
					continue;
				}
				boolean[][] tmpS = new boolean[HI][WI] ;
				for(int i=0;i<S.length;i++){
					tmpS[i] = Arrays.copyOf(S[i], S[i].length);
				}
				//ある道から幅優先で探索し経路の長さを全探索する
			 	ans = Math.max(BWS(w, h,tmpS),ans);
			}
		}

		System.out.println(ans);
	}

	public static int BWS(int w , int h,boolean[][] S){
		int len = 0;
		ArrayList<int[]> queue = new ArrayList<int[]>();
		int[] p = {w,h};
		queue.add(p);
		//現在地は壁に変更する
		S[p[0]][p[1]]=false;

		while(queue.size()!=0){
			ArrayList<int[]> queue2 = new ArrayList<int[]>();
			while(queue.size()!=0){
				p = queue.get(0);
				queue.remove(0);

				//pの上下左右で道があれば追加
				for(int i=0;i<4;i++){
					int[] aftP = {p[0]+around[i],p[1]+around[i+1]};
					if(S[aftP[0]][aftP[1]]){
						S[aftP[0]][aftP[1]]=false;
						queue2.add(aftP);
					}
				}
			}
			if(queue2.size()!=0){
				len++;
				queue=queue2;
			}
//			System.out.println(" ");
//		print(S);
		}

		return len;
	}

	public static void print(boolean[][] S){
		for(int i=0;i<S.length;i++){
			for(int k=0;k<S[0].length;k++){
				if(S[i][k]){
					System.out.print(". ");
				}else{
					System.out.print("# ");
				}
			}
			System.out.println("");
		}
	}
}


Measured memory_bytes: 37144
//
//  Created by Vijay Bhati on 19/02/20.
//  Copyright © 2019 Vijay Bhati. All rights reserved.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <map>
#include <sstream>
#include <set>
#include <iomanip>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cassert>
#include <memory>
#define ll long long
#define ull unsigned long long
#define pi acos(-1.0)
#define rf freopen("in.txt", "r", stdin);
#define ld long double
#define all(v) v.begin(),v.end()
#define pb push_back
#define P pair<ll, ll>
#define ff first
#define ss second
#define F first
#define S second
#define MOD 1000000007
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)

using namespace std;

ll max(ll a, ll b) {
    return a > b ? a : b;
}

ll min(ll a, ll b) {
    return a > b ? b : a;
}

ll __gcd(ll a, ll b) {
    if (a == 0) {
        return b;
    }
    return __gcd(b%a, a);
}

ll find_power(ll a, ll b) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = (ans * a) % 1000000007;
        }
        b = b >> 1;
        a = (a * a) % 1000000007;
    }
    return ans;
}

int main() {
#ifdef __APPLE__
    const clock_t begin_time = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    
    ll n, k, weight, cost, mx = 0;
    cin >> n >> k;

    ll dp[100005], w[105], v[105];

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

	for (int i = 0; i < 100005; i++) {
        dp[i] = 1e18;
    }

	dp[0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=100000;j>=v[i];j--){
			dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
		}
	}

	ll ans = 0;

    for (int i = 0; i <= 100000; i++) {
        if (dp[i] <= k)
            mx = max(mx, i * (ll)1);
    }
    
    cout << mx << endl;
    
    
#ifdef __APPLE__
    cout << endl;
    cout << "Time : ";
    cout << float( clock () - begin_time ) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}


Measured memory_bytes: 1024
//
// Created by kuroneko on 2019-07-06.
//

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>

typedef long long ll;
using namespace std;

int main() {
    int c_time[5];
    for (int i = 0; i < 5; i++) cin >> c_time[i];

    int res = 0;
    int residual[5];
    for (int i = 0; i < 5; i++) {
        residual[i] = (10 - c_time[i] % 10) % 10;
    }

    sort(residual, residual+5);
    for (int i = 0; i < 5; i++) {
        res += c_time[i];
        if (i != 4) res += residual[i];
    }
    cout << res << endl;
    return 0;
}

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

int main()
{
	int n, s, res;
	while (cin >> n >> s, n || s) {
		res = 0;
		for (int i = 1; i < 0x400; i++) {
			int digit = 0, sum = 0;
			for (int j = 0;j < 10; j++) {
				if ((i >> j) & 1) {
					digit++;
					sum += j;
				}
			}
			if (digit == n && sum == s) {
				res++;
			}
		}
		cout << res << endl;
	}
	return 0;
}

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

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

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

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

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

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

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

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

fn factorial(n: usize) -> usize {
    (0..n).map(|i| i + 1).fold(1, |acc, x| acc * x)
}

fn order(ns: &[usize]) -> isize {
    let mut appeared = vec![false; ns.len()];
    let mut count = 0;
    for (i, &n) in ns.into_iter().enumerate() {
        let order = appeared
            .iter()
            .enumerate()
            .filter(|&(_, &f)| !f)
            .take_while(|&(i, _)| i < n)
            .count();
        count += ((order - 1) * factorial(ns.len() - 1 - i)) as isize;
        appeared[n - 1] = true;
    }

    count
}

fn main() {
    input! {
        n: usize,
        ps: [usize; n],
        qs: [usize; n]
    }
    println!("{}", (order(&qs) - order(&ps)).abs());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <boost/algorithm/string.hpp>
using namespace std;
using boost::algorithm::split;

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

    string s;
    vector<string> vs; 
    getline(cin, s);
    split(vs, s, boost::is_space());

    const int L = 21; 
    int S = 0;
    for (int i = 0; i < 3; ++i){
        S += stoi(vs[i]);
    }

    if (S <= L) {
        cout << "win\n";
    }
    else {
        cout << "bust\n";
    }

    return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE FlexibleContexts #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IMS
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import qualified Data.Sequence as Seq
import Data.Sequence (Seq)
import qualified Data.Array.IArray as A
import qualified Data.Array.MArray.Safe as A
import qualified Data.Array.MArray as A
import Data.Array (Array)
import Data.Array.Unboxed (UArray)
import Data.Array.IArray (IArray)
import Data.Array.MArray.Safe (MArray)
import Data.Array.IO.Safe (IOArray, IOUArray)
import Data.Array.ST.Safe (STArray, STUArray, runSTArray, runSTUArray)
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Monad.ST
-- import Control.Monad.ST.Safe
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Control.Monad.State.Strict
import Data.Int
import System.IO
import Data.Function
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.STRef
import Data.IORef

main :: IO ()
main = do
  [n,h,w] <- replicateM 3 $ read <$> getLine :: IO [Int]
  print $ (n-h+1) * (n-w+1)


Measured memory_bytes: 508
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      PrintWriter w = new PrintWriter(System.out);
      
      char a[]=sc.next().toCharArray();
      char b[]=sc.next().toCharArray();
      
      int dp[][] = new int[a.length+1][b.length+1];
      
      for(int i=0;i<=a.length;i++)
      {
          for(int j=0;j<=b.length;j++)
          {
              if(i == 0 || j == 0)
              {
                  dp[i][j] = 0;
              }
              else if(a[i-1] == b[j-1])
              {
                  dp[i][j] = dp[i-1][j-1]+1;
              }
              else
              {
                  dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
              }
          }
      }
      
      int i = a.length, j = b.length;
      String ans = "";
      while(i>0 && j>0)
      {
          if(a[i-1]==b[j-1])
          {
              ans = a[i-1] + ans;
              i--;
              j--;
          }
          else
          {
              if(dp[i-1][j] >= dp[i][j-1])
              {
                  i--;
              }
              else
              {
                  j--;
              }
          }
      }
      w.println(ans);
      w.close();
    }
}

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

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

    int d_sum = 0;
    rep(i, N.size()) d_sum += N[i] - '0';

    if(d_sum % 9 == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3696
#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int, int> P;
const long long mod = 1000000007;
const int L = 26;
int rwa[26][200006];
int nxt[26][200006];
int jump[200006];//iから始めたときの終わり
int dp[200006];
signed main() {
	string s; cin >> s;
	int n = s.size();
	rep(i, L)rep(j, n)nxt[i][j] = n;
	rep(i, n) {
		rwa[s[i] - 'a'][i + 1]++;
		nxt[s[i] - 'a'][i] = i;
	}
	rep(i, n)rep(j, L)rwa[j][i + 1] += rwa[j][i];
	rep(i, L) {
		for (int j = n - 1; j > 0; j--) {
			nxt[i][j - 1] = min(nxt[i][j - 1], nxt[i][j]);
		}
	}
	rep(i, n) {
		int l = i-1, r = n;
		int c = 0;
		while (r - l > 1) {
			int mi = (r + l) / 2;
			rep(j, L) {
				if (rwa[j][mi+1] - rwa[j][i])c++;
			}
			if (c==L)r = mi;
			else l = mi;
			c = 0;
		}
		rep(j, L)if (rwa[j][r] - rwa[j][i])c++;
		if(c==L)jump[i] = l;
		else jump[i] = r;
	}
	dp[n] = 1;
	for (int i = n - 1; i >= 0; i--)dp[i] = dp[jump[i]+1] + 1;

	string ans;
	int now = 0;
	while (now < n) {
		rep(j, L) {
			int nn = nxt[j][now];
			if (dp[nn+1] + 1 + ans.size() == dp[0]) {
				ans.push_back('a' + j); 
				now = nn + 1;
				break;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 84996
import Data.List
import Control.Monad
import Data.Functor

main::IO ()
main=
  do
    n <- read <$> getLine::IO Int
    when (n>0) $ do
      input <- replicateM n getLine
      let toCard=(\(a:b:_)->(a,b)) . map read . words::String->(Int,Int)
          cards=map toCard input
          (ansA,ansB)=foldl' (\(a0,b0) (a,b) ->
                            case compare a b of
                              LT->(a0,b0+a+b)
                              GT->(a0+a+b,b0)
                              EQ->(a0+a,b0+b)
                              )
                              (0,0) cards
      putStrLn $ show ansA ++ ' ' : show ansB
      main

Measured memory_bytes: 7532
#include<stdio.h>
static const int MAX = 100;
static const int INFTY = (1<<21);

int main(){
  int M[MAX][MAX];
  int d[MAX];
  int p[MAX];
  int c[MAX];
  int n,i,j,a,sum,m,u,v;

  scanf("%d", &n);

  for(i = 0;i < n;i++){
    for(j = 0;j < n;j++){
      scanf("%d",&a);
      M[i][j] = (a==-1)?INFTY:a;
    }
  }

  for(i = 0;i < n;i++){
    d[i] = INFTY;
    p[i] = -1;
    c[i] = 0;
  }

  d[0] = 0;

  while(1){
    m = INFTY;
    u = -1;
    for(i = 0;i < n;i++){
      if(m > d[i] && !c[i]){
	u = i;
	m = d[i];
      }
    }
    if(u == -1)break;
    c[u] = 1;
    for(v = 0;v < n;v++){
      if(!c[v] && M[u][v] != INFTY){
	if(d[v] > M[u][v]){
	  d[v] =  M[u][v];
	  p[v] = u;
	}
      }
    }
  }
  sum = 0;
  for(i = 0;i < n;i++){
    if(p[i] != -1){
      sum += M[i][p[i]];
    }
  }
  printf("%d\n",sum);
}



Measured memory_bytes: 2052
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,sum=100000;
	scanf("%d",&n);
	for(int i=1;i<=n/2;i++){
		int a=i;
		int b=n-i;
		int ans=0;
		while(a){
			ans=ans+a%10;
			a=a/10;
		}
		while(b){
			ans=ans+b%10;
			b=b/10;
		}
		sum=min(sum,ans);
	}
	printf("%d\n",sum);
}

Measured memory_bytes: 256
n = int(input())
ttt = list(map(int, input().split()))
m = int(input())
pxs = [list(map(int, input().split())) for _ in range(m)]
sum_t = sum(ttt)
for i in range(m):
    print(sum_t - ttt[pxs[i][0] - 1] + pxs[i][1])


Measured memory_bytes: 3060
import sys
import heapq
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= -1
heapq.heapify(a)
 
for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))
    
print(sum(a)*(-1))

Measured memory_bytes: 14168
/*
この問題はABC_043_Aである
N人の子供を順番に並べて一人目には1個、二人目には2個と、続けていき、N人目にはN個渡す
全部で何個のキャンディーがいるかという話
*/
#include<iostream>
using namespace std;

int main(void){
  int n;
  cin >> n;
  int ans = 0;
  for(int i = 1;i <= n;i++){
    ans += i;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>

#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

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

int main() {
    int N;
    cin >> N;
    map<string, int> m;
    string ret;
    rep(i, N) {
        cin >> ret;
        m[ret]++;
    }
    cout << "AC x " << m["AC"] << endl;
    cout << "WA x " << m["WA"] << endl;
    cout << "TLE x " << m["TLE"] << endl;
    cout << "RE x " << m["RE"] << endl;

    return 0;
}


Measured memory_bytes: 3232
from collections import deque
n = int(input())
d = [-1]*n
d[0] = 0
M = []
for i in range(n):
    adj = list(map(int,input().split()))
    if adj[1] == 0:
        M += [[]]
    else:
        M += [adj[2:]]
Q = deque([0])

while Q != deque([]):
  u = Q.popleft()
  for i in range(len(M[u])):
    v = M[u][i]-1
    if d[v] == -1:
      d[v] = d[u] + 1
      Q.append(v)
for i in range(n):
  print(i+1,d[i])
                 
                 
  


Measured memory_bytes: 6036
#include <cstdlib>
#include <iostream>

using namespace std;

int main() {
  int a, b;

  scanf("%d %d", &a, &b);
  if (a > b) {
    int tmp = a;
    a = b;
    b = tmp;
  }

  for (int k = a; k < b; k++) {
    if ((a - k) == -(b - k)) {
      cout << k << endl;
      return 0;
    }
  }

  cout << "IMPOSSIBLE" << endl;

  return 0;
}


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

int main() {
    long long K;
    cin >> K;
    long long sum=0;
    for (long long i=1; i<=1000000; i++) {
        sum=sum*10+7;
        sum=sum%K;
        if (sum==0) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}

Measured memory_bytes: 3596
import java.util.*;

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

		Scanner sc = new Scanner(System.in);

		int X = sc.nextInt();
		
		int max=1;
		for(int t=2;t<=(int)Math.sqrt(X);t++){
			int s=1;
			while((int)Math.pow(t,s) <= X){
				s++;
			}
			if(max < (int)Math.pow(t,s-1)) max = (int)Math.pow(t,s-1);
		}

		System.out.println(max);
		
	}
}

Measured memory_bytes: 23252
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>

using namespace std;

int main(){
  int P, Q, R;
  cin >> P >> Q >> R;
  cout << P+Q+R-max({P,Q,R}) << endl;;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  long long X,M;
  cin>>X>>M;
  long long answer=0;
  long long A=X;
  if(N>M){
  long long rot[100000];
  for(int i=0;i<M;i++){
    rot[i]=A;
    answer+=A;
    A=(A*A)%M;
  }
  long long roop=1;
  long long S=rot[M-roop];
  while(A!=rot[M-roop]){
    roop++; S+=rot[M-roop];
  }
  answer+=((N-M)/roop)*S;
  for(long long i=0;i<(N-M)%roop;i++){
    answer+=A; A=(A*A)%M;
  }
  }
  else{
    for(int i=0;i<N;i++){
      answer+=A; A=(A*A)%M;
    }
  }
  cout<<answer<<endl;
  
  return 0;
}

Measured memory_bytes: 3976
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;

int main() {
  string s;
  cin >> s;
  if (s[0] == 'S') cout << "Cloudy" << endl;
  else if (s[0] == 'C') cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000
#define MAX_I 100000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, result = 0, t[100000], c[100000];
  cin >> n;
  vector<ll> vec;
  vec.pb(1);
  ll i = 1;
  while (1) {
    ll sum = pow(6, i);
    vec.pb(sum);
    if (sum > n) break;
    i++;
  }
  i = 1;
  while (1) {
    ll sum = pow(9, i);
    vec.pb(sum);
    if (sum > n) break;
    i++;
  }
  sort(vec.begin(), vec.end());
  unique(vec.begin(), vec.end());
  i = 1;
  for(auto x : vec) {
    c[i] = x;
    i++;
  }
  rep(i, MAX_I + 1) t[i] = INF;
  t[0] = 0;
  for(int i = 0; i < vec.size(); i++) {
    for(int j = c[i]; j <= n; j++) {
      t[j] = min(t[j], t[j - c[i]] + 1);
    }
  }
 cout << t[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
n = gets.to_i

keta = n.to_s.length
case keta
when 1 then
    puts n
when 2 then
    puts 9
when 3 then
    puts n - 99 + 9 
when 4 then
    puts 9 + 900
when 5 then
    puts n - 9999 + 9 + 900
when 6 then
    puts 9 + 900 + 90000
end

Measured memory_bytes: 3836
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

int a[10];


int main()
{
	for(int i = 0; i < 3; i++){
		cin >> a[i];
	}
	sort(a,a+3);
	if(a[0]==5 && a[1]==5 && a[2] == 7){
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 888
H,W=map(int,input().split())
N=int(input())
A=list(map(int,input().split()))

ans=[]
for i in range(N):
    for j in range(A[i]):
        ans.append(i+1)

for y in range(H):
    x=ans[y*W:y*W+W]
    if y%2!=0:
        x.reverse()
    print(*x)

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

#define MAX 2000001
#define VMAX 10000

int main(){
  int *A,*B,C[VMAX],n,i,j;

  scanf("%d",&n);

  A = malloc(sizeof(int)*n+1);
  B = malloc(sizeof(int)*n+1);

  for ( i = 0; i <= VMAX; i++ ) C[i] = 0;

  for ( i = 0; i < n; i++ ){
    scanf("%d", &A[i + 1]);
    C[A[i + 1]]++;
  }

  for ( i = 1; i <= VMAX; i++ ) C[i] = C[i] + C[i - 1];

  for ( j = 1; j <= n; j++ ){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", B[i]);
  }
  printf("\n");

  return 0;

}

Measured memory_bytes: 16276
//ITP1_5_B
//

using System;
using System.Collections.Generic;



class Program
{
    static void Main(string[] args)
    {
        int[] h = new int[50];
        int[] w = new int[50];

        int count = 0;

        while (true)
        {
            //?????????????????????????????????int??????iaaray????????????????????\

            int[] iarray = Array.ConvertAll<string, int>((Console.ReadLine().Split(' ')), delegate (string value)
            {
                return int.Parse(value);
            });

            h[count] = iarray[0];
            w[count] = iarray[1];

            if (h[count] == 0 && w[count] == 0)
                break;
            count++;

        }

        for (int c = 0; c < count; c++)
        {
            for (int i = 0; i < h[c]; i++)
            {
                for (int j = 0; j < w[c]; j++)
                {
                    if (i == 0 || i == h[c] - 1 || j == 0 || j == w[c]- 1)
                    {
                        Console.Write("#");
                    }
                    else
                    {
                        Console.Write(".");
                    }
                }
                Console.Write("\r\n");
            }
            Console.Write("\r\n");
        }

    }
}

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

typedef long int lint;
typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<long, long> pll;

#define EACH(t, c) for (auto&& t : c)
#define ALL(c) begin(c), end(c)
#define FOR(i, s, e) for (int i = (s); i < (int)(e); ++i)
#define REP(i, n) FOR(i, 0, n)
#define endl '\n'
#define fk first
#define sv second

const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

template<typename T>
void print(const std::vector<T>& v, char sep=' ') {
  for (int i = 0; i < (int)v.size(); i++) {
    if (i != 0) cout << sep;
    cout << v[i];
  }
  cout << endl;
}

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

  REP(i, 9) {
    REP(j, 9) {
      cout << (i + 1) << "x" << (j + 1) << "=" << (i + 1) * (j + 1) << endl;
    }
  }
}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=200005;
int n,l,tot;
int a[maxn],now[maxn*2],nnow[maxn*2],pre[maxn*2];
int val[maxn*2],vl[maxn*2],vr[maxn*2],suml[maxn*2],sumr[maxn*2];
ll ans;
class Cmp{
public:
	bool operator ()(const int &a,const int &b){
		if(val[a]!=val[b])return val[a]<val[b];
		return vl[a]<vl[b];
	}
};
set<int,Cmp>s;

int main(){
	scanf("%d%d",&n,&l);
	REP(i,n){
		scanf("%d",&a[i]);
		tot++;
		vl[tot]=vr[tot]=i;
		val[tot]=a[i];
		suml[tot]=sumr[tot]=1;
		s.insert(tot);
	}
	while(!s.empty()){
		int len=0;
		now[++len]=*s.begin();
		s.erase(s.begin());
		while(!s.empty()&&val[*s.begin()]==val[now[1]]&&vl[*s.begin()]==vr[now[len]]+1){
			now[++len]=*s.begin();
			s.erase(s.begin());
		}
		pre[0]=0;
		REP(i,len)pre[i]=pre[i-1]+suml[now[i]];
		REP(i,len){
			ans+=1LL*suml[now[i]]*sumr[now[i]];
			if(i-l+1>=1)ans+=1LL*sumr[now[i]]*pre[i-l+1];
		}
		int nlen=0,last=0;
		REP(i,len/l){
			int tmpl=(i-1)*l+1,tmpr=i*l;
			if(i==len/l)tmpr=len;
			tot++;
			vl[tot]=vl[now[tmpl]];vr[tot]=vr[now[tmpr]];
			val[tot]=val[now[1]]+1;
			for(int j=i*l;j<=(i+1)*l-1&&j<=len;j++)sumr[tot]+=sumr[now[j]];
			suml[tot]=pre[len%l+1+(i-1)*l]-pre[last];
			last=len%l+1+(i-1)*l;
			s.insert(tot);
			nnow[++nlen]=tot;
		}
		pre[0]=0;
		REP(i,nlen)pre[i]=pre[i-1]+suml[nnow[i]];
		REP(i,nlen){
			ans-=1LL*suml[nnow[i]]*sumr[nnow[i]];
			if(i-l+1>=1)ans-=1LL*sumr[nnow[i]]*pre[i-l+1];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) std::cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << '\n';
}

void solve() {
    Int n;
    cin >> n;
    vector<Int> p(n);
    for (Int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    Int res = 0;
    for (Int i = 0; i < n; i++) {
        if (p[i] == i) {
            res++;
            if (i < n - 1 and p[i + 1] == i + 1) {
                swap(p[i], p[i + 1]);
            }
        }
    }
    print(res);
}

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


Measured memory_bytes: 4036
from collections import deque


def solve():
    H, W = map(int, input().split())
    C_h, C_w = map(lambda x: int(x) - 1, input().split())
    D_h, D_w = map(lambda x: int(x) - 1, input().split())
    field = [list(input()) for _ in range(H)]
    dp = [[float("inf")] * W for _ in range(H)]
    dp[C_h][C_w] = 0

    q = deque([(C_h, C_w)])
    visited = set()
    while q:
        i, j = q.popleft()
        if (i, j) in visited:
            continue
        visited.add((i, j))
        for di in range(-2, 3):
            for dj in range(-2, 3):
                if (di, dj) == (0, 0):
                    continue
                ni = i + di
                nj = j + dj
                if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                    continue

                if (di, dj) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j])
                    q.appendleft((ni, nj))
                else:
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 1)
                    q.append((ni, nj))
    ans = dp[D_h][D_w]
    print(-1) if ans == float("inf") else print(ans)


solve()


Measured memory_bytes: 218084
import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
dist = [-1] * N
d = 1
dl = []
pre[0] = 0
dist[0] = 0
dl.append(0)

while(len(dl) != 0) :
    a = dl[0]
    dl.pop(0)
    for i in res[a] :
        if(dist[i] != -1):
            continue
        dist[i] = dist[a] + 1
        pre[i] = a
        dl.append(i)
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

Measured memory_bytes: 35068
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
int main(void) {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> a(n + 1, 0);
  rep(rv, 2) {
    int cnt = 0;
    rep(i, n) {
      if(s[i] == '<') {
        cnt++;
        a[i + 1] = max(a[i + 1], cnt);
      } else {
        cnt = 0;
      }
    }
    reverse(s.begin(), s.end());
    rep(i, n) {
      if(s[i] == '<')
        s[i] = '>';
      else
        s[i] = '<';
    }
    reverse(a.begin(), a.end());
  }
  ll ans = 0;
  rep(i, n + 1) ans += a[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2820
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N  =  2e5 + 5, MOD  =  1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int l[N], r[N], pre[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin>>n>>m;

    for(int i = 1; i <= m; i++){
        cin>>l[i]>>r[i];
        pre[l[i]]++;
        pre[r[i] + 1]--;
    }

    for(int i = 1; i < N - 5; i++){
        pre[i] += pre[i - 1];
    }
    int cnt = 0;
    for(int i = 1; i < N - 5; i++){
        if(pre[i] == m) cnt++;
    }
    cout<<cnt;


    return 0;
}


Measured memory_bytes: 4352
<?php
# スペース区切りの整数の入力
fscanf(STDIN, "%d %d %d", $a, $b, $c);
$goshichigo = 'NO';
if ( $a == 7 ) {
  if ( $b == 5 && $c == 5) {
    $goshichigo = 'YES';
  }
} elseif ( $b == 7 ) {
  if ( $a == 5 && $c == 5) {
    $goshichigo = 'YES';
  }
} elseif ( $c == 7 ) {
  if ( $a == 5 && $b == 5) {
    $goshichigo = 'YES';
  }
}
# 出力
echo $goshichigo."\n";
?>

Measured memory_bytes: 3576