akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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

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


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "[";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        if (it != mp.begin()) {
            os << ", ";
        }
        os << *it;
    }
    return os << "]";
}

// edit

void solve() {
    int N;
    string S;
    cin >> N >> S;

    int L = 0, R = N - 1;
    int ans = 0;
    while (R > L) {
        if (R <= L) break;
        if (S[L] == 'R') L++;
        if (S[R] == 'W') R--;
        if (R > L && S[L] == 'W' && S[R] == 'R') {
            swap(S[L], S[R]);
            ans++;
        }
    }
    cout << ans << endl;


}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


Measured memory_bytes: 3464
N, M = map(int, input().split())
stu = list(list(map(int, input().split())) for _ in range(N))
gol = list(list(map(int, input().split())) for _ in range(M))


for i in range(N):
    l_new = 10 ** 16
    num = 0
    for j in range(M):
        l_old = abs(stu[i][0] - gol[j][0]) + abs(stu[i][1]-gol[j][1])
        if l_old < l_new:
            l_new = l_old
            num = j+1
    print(num)

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

#define FOR(i, a, b) for (int i=(a); i < (b); i++)
#define RFOR(i, b, a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 10100;


int main()
{
//	freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);
	string s;
	cin>>s;
	int bal = 0;
	int ans = 0;
	FOR(i,0,SZ(s))
	{
		if(s[i]=='g')
		{
			if(bal>0)ans++,bal--;
			else bal++;
		}
		else
		{
			if(bal>0)bal--;
			else ans--,bal++;
		}
	}

	cout<<ans;
}


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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;




int main(){
  ll n, k;
  cin >> n >> k;


  if((n-1)*(n-2)/2 < k){
    cout << -1 << endl;
    return 0;
  }
  

  vector<set<ll>> g(n, set<ll>());

  rep(i, n-1){
    g[0].insert(i+1);
    g[i+1].insert(0);
  }

  ll sum = (n-1)*(n-2)/2;

  ll l = 1;
  ll r = 2;
  while(k < sum){
    g[l].insert(r);
    g[r].insert(l);
    if(r == n-1) l++, r = l+1;
    else         r++;
    sum--;
  }

  cout << n-1 + (n-1)*(n-2)/2 - k << endl;
  rep(l, n){
    for(auto r : g[l]){
      if(l < r) cout << l+1 << " " << r+1 << endl;
    }
  }



  return 0;
}


Measured memory_bytes: 768
/*
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
 */
import java.util.*;

public class Main {
	
	int[] A;
	int nSwap = 0;
	
	void printArray(int[] a) {
		System.out.print(a[0]);
		for (int i = 1; i < a.length; i++) {
			System.out.print(" " + a[i]);
		}
		System.out.println();
	}
	
	void merge(int left, int mid, int right) {
		//System.out.println("#: " + left + ", " + mid + ", " + right);
		//printArray(A);
		int n1 = mid - left;
		int n2 = right - mid;
		int[] L = new int[n1+1];
		int[] R = new int[n2+1];
		for (int i = 0; i < n1; i++) L[i] = A[left + i];
		for (int i = 0; i < n2; i++) R[i] = A[mid + i];
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;
		int i = 0, j = 0;
		for (int k = left; k < right; k++) {
			nSwap++;
			if (L[i] <= R[j]) {
				A[k] = L[i];
				i++;
			} else {
				A[k] = R[j];
				j++;
			}
		}
		//printArray(A);
		//System.out.println();
	}
	
	void mergeSort(int left, int right) {
		if (left + 1 < right) {
			int mid = (left + right) / 2;
			mergeSort(left, mid);
			mergeSort(mid, right);
			merge(left, mid, right);
		}
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		A = new int[n];
		for (int i = 0; i < n; i++) {
			A[i] = sc.nextInt();
		}
		mergeSort(0, A.length);
		printArray(A);
		System.out.println(nSwap);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}



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

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

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


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
ll dp[1000005][2][2];

int main(){
	ll n;
	cin >> n;
	dp[1][0][0]=8;
	dp[1][1][0]=1;
	dp[1][0][1]=1;
	dp[1][1][1]=0;
	for(int i=2;i<=n;i++){
		dp[i][1][1]=(((dp[i-1][1][1]*10)%MOD+(dp[i-1][0][1])%MOD)%MOD+dp[i-1][1][0])%MOD;
		// cout << dp[i][1][1] << '\n';
		dp[i][0][1]=((dp[i-1][0][1]*9)%MOD+dp[i-1][0][0])%MOD;
		// cout << dp[i][0][1] << '\n';
		dp[i][1][0]=((dp[i-1][1][0]*9)%MOD+dp[i-1][0][0])%MOD;
		// cout << dp[i][1][0] << '\n';
		dp[i][0][0]=(dp[i-1][0][0]*8)%MOD;
		// cout << dp[i][0][0] << '\n';
	}
	cout << dp[n][1][1] << '\n';
}

Measured memory_bytes: 34764
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    immutable int M = 30;
    
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto B = readln.split.map!(to!int).array;
    
    auto B_bits = new int[][](M);
    foreach (i; 0..N) foreach (j; 0..M) B_bits[j] ~= (B[i] & ((1<<(j+1))-1));
    foreach (j; 0..M) B_bits[j].sort();

    int ans = 0;
    
    foreach (i; 0..N) {
        foreach (j; 0..M) {
            int a = A[i] & ((1 << (j + 1)) - 1);
            int x = ((1 << j) - 1) - (a & ((1 << j) - 1)) + 1;
            int y = x + (1 << j);
            int lb = B_bits[j].assumeSorted.lowerBound(x).length.to!int;
            int ub = B_bits[j].assumeSorted.upperBound(y-1).length.to!int;
            int one = lb + ub;
            if ((a >> j) == 0) one = N - one;
            one &= 1;
            ans ^= (one << j);
        }
    }

    ans.writeln;
}


Measured memory_bytes: 60072
#include <cstdlib>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <functional>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << ((a * b) % 2 == 0 ? "Even" : "Odd") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <memory.h>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <queue>
#include <stack>
#include <cstdio>
#include <bitset>

using namespace std;

#define nfs ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define ii pair<int,int>
#define iii pair<int,pair<int,int> >
#define ll long long
#define ull unsigned long long
#define ld long double
#define ef else if
#define loc(x) (x).begin(),(x).end() 
#define locR(x) (x).rbegin(),(x).rend()
#define no puts("NO")
#define yes puts("YES")
#define ex puts("-1")
#define en puts("")
#define _ cout  
#define __ <<
#define outV(v) for(int i = 0 ; i < v.size() ; i++)cout << v[i] << ' ';
#define outA(x,l,r) for(int i = l ; i < r ; i++)cout << x[i] << ' ';

const ld EPS = 1e-18;
const double DEPS = 1e-9;
const ld PI = 3.141592653589793238;
const ull MOD = 1e9 + 7;
const int N = (int)(5e5) + 1;

ll gcd(ll fx, ll fy)
{
	if (!fy) return fx;
	return gcd(fy, fx % fy);
}

inline void fill(int* ar, int sz, int val)
{
	for (int i = 0; i < sz; i++)
	{
		ar[i] = val;
	}
}

int n, k;
ll dp[N][101], w[101], v[101];

ll rec(int cur,int idx)
{
	if (cur < 0)return -1e9;
	if (idx == n) return (cur >= 0 ? 0 : -1e9);
	ll& dp = ::dp[cur][idx];
	if (~dp)return dp;

	dp = rec(cur - w[idx], idx + 1) + v[idx];
	dp = max(dp, rec(cur, idx + 1));
	return dp;
}

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

	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", w + i, v + i);
	}
	ll ans = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if(j - w[i] >= 0)
				dp[j][i] = max(dp[j][i - 1], dp[j - w[i]][i - 1] + v[i]);

			dp[j][i] = max(dp[j][i], dp[j][i - 1]);

		}
	}

	printf("%lld", dp[k][n]);
}

Measured memory_bytes: 80128
#include <iostream>
#include <stack>
using namespace std;
int main() {
   // cout<<"Hello World!";
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin>>n;
   string s;
   cin>>s;
   stack<char> st;
   st.push(s[0]);
   for(int i=1;i<n;i++)
   {
       if(s[i]!=st.top())
       {
           st.push(s[i]);
       }
   }
   cout<<st.size();
}


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

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

	int cnt = 0;

	for (int i = 0; i < N; i++) {
		int h;
		cin >> h;
		if (h >= K) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
using ll = long long;

const long double PI = acos(-1.0);
const int MOD = 1e9 + 7;

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

    int ans = 0;
    if(s == "RRR") ans = 3;
    else if(s == "RRS" || s == "SRR") ans = 2;
    else if(s == "SSS") ans = 0;
    else ans = 1;
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000050;
int a[10000];
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(a[i]%2==0)
        {
            if(a[i]%3==0||a[i]%5==0) continue;
            cout<<"DENIED"<<endl;
            return 0;
        }
    }
    cout<<"APPROVED"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue> 
 
using namespace std;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int A, B, C;

	cin >> A >> B >> C;

	if(A == B) {
		if(A != C) {
			cout << "Yes" << endl;
			return 0;
		}
	} else if(B == C) {
		if(B != A) {
			cout << "Yes" << endl;
			return 0;
		}
	} else if(C == A) {
		if(C != B) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}

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

public class Main {

    public static void main(String[] args) {
        FastReader fs = new FastReader();
        int x = fs.nextInt();
        if (x == 1) System.out.println(0);
        else System.out.println(1);


    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 32804
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

const long long INF = 1e17+7;
const long long MOD = 1e9+7;
const double PI=acos(-1);

using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	vector<vector<int>> bfs(n+1);
	vector<int> cost(n+1,-1);
	vector<int> before(n+1,-1);
	vector<bool> check(n+1,false);
	queue<int> q;
	
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >> b;
		bfs[a].push_back(b);
		bfs[b].push_back(a);
	}
	
	cost[1]=0;
	check[1]=true;
	q.push(1);
	while(1){
		int now=q.front();
		q.pop();
		for(int v=0;v<bfs[now].size();v++){
			int node=bfs[now][v];
			if(check[node])continue;
			q.push(node);
			check[node]=true;
			cost[node]=cost[now]+1;
			before[node]=now;
		}
		if(q.empty())break;
	}
		
	cout << "Yes" << endl;	
	for(int i=2;i<=n;i++){
		cout << before[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 10656
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int p = sc.nextInt(), q = sc.nextInt(), r = sc.nextInt();
        int sum = p + q + r;
        int[] hoge = {p, q, r};
        System.out.println(Arrays.stream(hoge).map(operand -> sum - operand).min().getAsInt());
    }
}

Measured memory_bytes: 28116
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    long long n, k;
    cin >> n; cin >> k;
    long long cnt = 0;
    while (n != 0) {
        n /= k;
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include<cmath>
#define N 100005
#define A 1000005
#define MOD 1000000007 // //100000000 998244353 //
#define inf 1000000000000000000
#define ll long long
//#define M_PI 3.141592653589793238463

using namespace std;

#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define itr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define mem(a, b) memset(a, (ll)b, sizeof(a))
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount
#define ANS(s) {cout << s << "\n"; return;}

//~~~~~~fancy print~~~~~~~//
#define printpii(a) cout << a.ft << " " << a.sd << endl;
#define printpiii(a) cout << a.ft << " " << a.sd.ft << " " << a.sd.sd << endl;
#define print(a, n) rep(i, n) cout << a[i] << " "; cout << endl;
#define printv(v) for(auto x: v)cout << x << " "; cout << endl;
#define printm(a, n, m) rep(i, n) { rep(j, m) cout << a[i][j] << "\t"; cout << endl;}

ll lx[4] = {0, 0, 1, -1};
ll ly[4] = {1, -1, 0, 0};
ll dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
ll dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
void fast(){ios_base::sync_with_stdio(false);cin.tie(0);cout << setprecision(12) << fixed;}
ll lcm(ll a, ll b) {return (a*b)/__gcd(a, b); }

void solve()
{
    ll n, mn = inf;
    cin >> n;
    ll a[n];
    rep(i, n)
    {
        ll x; cin >> x;
        if(i == 0) a[i] = x;
        else a[i] = a[i-1]+x;
    }
    for(ll i = 0; i <n-1;i++){
        mn = min(mn, abs(a[n-1] - 2*a[i]));
    }
    cout << mn;
}
int main(){
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    fast();
    ll t = 1; //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
    cin>>a;
    b=a;
    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='b') a[i]='d';
        else if(a[i]=='d') a[i]='b';
        else if(a[i]=='p') a[i]='q';
        else if(a[i]=='q') a[i]='p';
    }
    if(a==b)
    cout<<"Yes";
    else
    cout<<"No";
    return 0;
}

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

int main() {
	int n;
	cin >> n;
	int mx = 0;
	int ans = 0;
	rep(i, n) {
		int p;
		cin >> p;
		mx = max(p, mx);
		ans += p;
	}
	cout << ans - mx / 2 << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"os"
	"sort"
)

func run() int {
	var n, k int
	fmt.Scanf("%d %d\n", &n, &k)
	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &h[i])
	}

	sort.Sort(sort.Reverse(sort.IntSlice(h)))

	for i := 0; i < k && len(h) > 0; i++ {
		h = h[1:len(h)]
	}

	cnt := 0
	for _, v := range h {
		cnt += v
	}

	fmt.Println(cnt)

	return 0
}

func main() {
	os.Exit(run())
}


Measured memory_bytes: 6528
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>

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

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
    int a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    if(a1 + a2 + a3 <= 21){
        cout << "win" << endl;
    }else{
        cout << "bust" << endl;
    }
}

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

class Dinic {
    using i64 = long long;
    struct Edge {
        int to;
        i64 cap;
        int rev;
        Edge(int t, i64 c, int r) : to(t), cap(c), rev(r) {}
    };

    std::vector<std::deque<Edge>> g;
    std::vector<int> level;
    std::vector<unsigned> iter;
    int size;

    void bfs(int s) {
        for (int i = 0; i < size; i++) level[i] = -1;
        level[s] = 0;

        std::deque<int> q { s };

        while (!q.empty()) {
            auto curr = q.front();
            q.pop_front();
            for (auto & e : g[curr]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[curr] + 1;
                    q.push_back(e.to);
                }
            }
        }
    }

    i64 dfs(int v, int t, i64 f) {
        if (v == t) return f;

        for (unsigned i = 0; i < g[v].size(); i++) {
            iter[v] = i;
            auto &e = g[v][i];

            if (e.cap > 0 && level[v] < level[e.to]) {
                i64 d = dfs(e.to, t, std::min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }

        return 0;
    }

public:
    static constexpr i64 inf = 1000000000000000;

    explicit Dinic(int s) :
        g(std::vector<std::deque<Edge>>(s)),
        level(std::vector<int>(s)),
        iter(std::vector<unsigned>(s)),
        size(s) {}

    void add_edge(int from, int to, i64 cap) {
        g[from].emplace_back(to, cap, g[to].size());
        g[to].emplace_back(from, 0, g[from].size() - 1);
    }

    i64 calc(int s, int t) {
        i64 flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;

            for (auto &el : iter) el = 0;

            i64 f = dfs(s, t, inf);
            while (f > 0) {
                flow += f;
                f = dfs(s, t, inf);
            }
        }
    }
};

int main() {
    int h, w;
    std::cin >> h >> w;

    Dinic d(h + w + 2);

    std::string in;
    for (int i = 0; i < h; i++) {
        std::cin >> in;
        for (int j = 0; j < w; j++) {
            char c = in[j];
            if (c == 'o') {
                d.add_edge(i, h + j, 1);
                d.add_edge(h + j, i, 1);
            } else if (c == 'S') {
                d.add_edge(h + w, i, Dinic::inf);
                d.add_edge(h + w, h + j, Dinic::inf);
            } else if (c == 'T') {
                d.add_edge(i, h + w + 1, Dinic::inf);
                d.add_edge(h + j, h + w + 1, Dinic::inf);
            }
        }
    }

    auto ret = d.calc(h + w, h + w + 1);
    if (ret >= Dinic::inf) ret = -1;
    std::cout << ret << std::endl;

    return 0;
}

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

const int MAX_V = 10000;

vector<int> g[MAX_V]; //??°??????
vector<int> tp; //????????????????????????????????????

void bfs(int s, int indeg[MAX_V], bool used[MAX_V]){
    queue<int> q;

    q.push(s);
    used[s] = true;

    while(not q.empty()){
        int u = q.front(); q.pop();
        tp.emplace_back(u);
        rep(i,g[u].size()){
            int v = g[u][i];
            indeg[v]--;
            if(indeg[v] == 0 && not used[v]){
                used[v] = true;
                q.push(v);
            }
        }
    }
}

//??°??????????????????????????´??????0?????????
bool topologicalSort(int v){
    int indeg[MAX_V]; //??\?¬???°
    bool used[MAX_V];
    memset(indeg, 0, sizeof(indeg));
    memset(used, 0, sizeof(used));

    rep(i,v) rep(j,g[i].size()) indeg[ g[i][j] ]++;
    rep(i,v) if(indeg[i] == 0 && not used[i]) bfs(i, indeg, used);

    for(auto it:tp) cout << it << endl;

    if(tp.size() == v) return true;
    else return false;
}

int main(){
    int v, e;
    cin >> v >> e;
    rep(i,e){
        int s, t;
        cin >> s >> t;
        g[s].emplace_back(t);
    }
    topologicalSort(v);
}

Measured memory_bytes: 3932
N = int(input())
S1 = str(input())
S2 = str(input())

# ドミノの並べ方を数えて行く
mod = 1000000007

pointa_s1 = 0
pointa_s2 = 0
if S1[pointa_s1] == S2[pointa_s2]:  # 縦に同じドミノからスタートする場合
    ans = 3
    pointa_s1 += 1
    pointa_s2 += 1
else:  # 横に同じドミノからスタートする場合
    ans = 6
    pointa_s1 += 2
    pointa_s2 += 2

while N > pointa_s1:
    # 分岐を色々考えていく
    if S1[pointa_s1] == S2[pointa_s2]:  # 縦に同じとき
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  # その前も縦に並んているなら
            ans *= 2
            pointa_s1 += 1
            pointa_s2 += 1
        else:  # その前が横に並んでいるなら
            ans *= 1
            pointa_s1 += 1
            pointa_s2 += 1
    else:  # 今見ているものが横に同じとき
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  # その前も縦に並んているなら
            ans *= 2
            pointa_s1 += 2
            pointa_s2 += 2
        else:  # その前が横に並んでいるなら
            ans *= 3
            pointa_s1 += 2
            pointa_s2 += 2

print(ans % mod)


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br =
				new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			int target = Integer.parseInt(br.readLine());
			if (target == 0) break;
			int sum = 0, ans = 0;
			for (int i = 1; i <= 12; i++) {
				String[] str = br.readLine().split(" ");
				sum += Integer.parseInt(str[0]) - Integer.parseInt(str[1]);
				if (sum >= target && ans == 0) ans = i;
			}
			System.out.println(ans == 0 ? "NA" : ans);
		}

	}

}

Measured memory_bytes: 30612
n = gets.to_i

Restaurant = Struct.new(:id, :city, :point) do
  include Comparable

  def <=>(other)
    result = self.city <=> other.city
    if result == 0
      result = other.point <=> self.point
    end

    result
  end
end
restaurants = []
n.times do |i|
  s, p = gets.split(' ')
  restaurants << Restaurant.new(i+1, s, p.to_i)
end
restaurants.sort.map(&:id).each do |id|
  print "#{id}\n"
end

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

int main(){
  string S;
  cin >> S;
  vector<string> day;
  day = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
  
  for (int i=0; i<7; i++){
	  if (S==day[i]){
	    cout << 7-i << endl;
	  }
  }
}

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

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int mod = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}

bool ok(ll x){
	ll l = 0, r = 1e3;
	while(l <= r){
		ll md = (l + r) / 2;
		if(md * md * md * md * md <= x) l = md + 1;
		else r = md - 1;
	}
	return r;
}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);	

	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x : a) cin >> x;
	ll res = 0;

	// 1 -> n - 1
	map<int, int> mp;
	for(int i = 0; i < n; ++i){
		res += mp[-(a[i] - i)];
		mp[a[i] + i]++;
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 21000
#include "bits/stdc++.h"

//region Template
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const int MOD = 1000000007;

using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;

#define finish(x) cout << x; exit(0);
#define fastIO cin.tie(0); cin.sync_with_stdio(false);

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }

//const string USCAO_TAG = "mountains";
void usaco(const string& USACO_TAG) { setIn(USACO_TAG + ".in"); setOut(USACO_TAG + ".out"); }
void print() {}
template<typename T, typename... Args>
void print(T firstArg, Args... args) {
	#ifdef LOCAL
	cout << firstArg << "\t";
	print(args...);
	#endif
}
//endregion

/* Notes:
 * Farah </3
 */

const int MAXN = 3e5 + 6;
const ll INF = 2e18;

ll mx[MAXN], mn[MAXN];
ll a[MAXN];

multiset<int> s, v;

int main() {
	#ifdef LOCAL
	setIn("in.txt");
	setOut("out.txt");
	#endif

	int n;
	cin >> n;

	for(int i = 0; i < 3 * n; i++){
		cin >> a[i];
	}

	ll cur = 0;
	for(int i = 0; i < 3 * n; i++){
		if(s.size() >= n){
			auto mn = *s.begin();
			if(mn < a[i]){
				s.erase(s.begin());
				s.insert(a[i]);

				cur -= mn;
				cur += a[i];
			}
		}
		else{
			cur += a[i];
			s.insert(a[i]);
		}

		mx[i] = cur;
	}

	cur = 0;
	for(int i = 3 * n - 1; i >= 0; i--){
		if(v.size() >= n){
			auto x = *(v.begin());
			if(x < -a[i]){
				v.erase(v.begin());
				v.insert(-a[i]);

				cur -= -x;
				cur += a[i];
			}
		}
		else{
			cur += a[i];
			v.insert(-a[i]);
		}

		mn[i] = cur;
	}

	ll ans = -INF;
	for(int i = n - 1; i < 2 * n; i++){
		ans = max(ans, mx[i] - mn[i + 1]);
	}

	cout << ans;
}


Measured memory_bytes: 16640
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <bitset>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
char s[109];
int main()
{
    while(~scanf("%s",s))
    {
        s[5]=' ';
        s[13]=' ';
        printf("%s\n",s);
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int b,c,d;
int main()
{
	int n;
	cin>>n;
	for (int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		if (a%4==0)
			b++;
		else
			if (a%2==0)
				c++;
			else
				d++;
	}
	if (d>b+1||(d==b+1&&c!=0)) cout<<"No";
	else cout<<"Yes";
	return 0;
}

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

typedef long long ll;

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

	int times, cnt = 0;
	cin >> times;
	int dice1, dice2;
	while (times--)
	{
		cin >> dice1 >> dice2;
		if (dice1 == dice2)
			++cnt;
		else
			cnt = 0;
		if (cnt > 2)
			break;
	}
	if (cnt > 2)
		cout << "Yes\n";
	else
		cout << "No\n";
	return 0;
}

Measured memory_bytes: 3632
def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = 0
    for i, a in enumerate(A):
        if i % 2 == 0 and a % 2 == 1:
            c += 1


    return c

print(main())
#print('Yes' if main() else 'No')
#print('YES' if main() else 'NO')


Measured memory_bytes: 9164
L =[]

N = int(input())

for i in range(N):
    S = input()
    L.append(S)

print("AC x " + str(L.count("AC")))
print("WA x " + str(L.count("WA")))
print("TLE x " + str(L.count("TLE")))
print("RE x " + str(L.count("RE")))

Measured memory_bytes: 16072
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9,MOD = 1e9+7,ohara = 1e6;
const ll LINF = 1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>x>>y;
    if(abs(x-y)<=1)Cout("Brown");
    else Cout("Alice");
    return 0;
}


Measured memory_bytes: 256
from collections import deque

n = int(input())

ab = [list(map(int,input().split())) for i in range(n-1)]

ver = [[] for i in range(n)]

for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)

#print(ver)

color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1

#print(q)

while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1

#print(color)
k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])


Measured memory_bytes: 74912
use proconio::{fastout, input};
use rand::Rng;
use std::collections::BTreeSet;

#[fastout]
fn main() {
   input! {
      dn: usize,
      c: [i64; 26],
      mut s: [[i64;26]; dn],
   }

   s.insert(0, vec![]);
   let mut t = vec![0];
   let mut last = vec![BTreeSet::new(); 26];
   let start = std::time::Instant::now();
   let time_limit = std::time::Duration::from_millis(1950);

   for i in 0..26 {
      last[i].insert(0);
      last[i].insert(dn + 1);
   }
   for d in 1..=dn {
      let mut mx = std::i64::MIN;
      let mut tn = 0;
      for t in 0..26 {
         let mut score = 0i64;
         score += s[d][t];
         for j in 0..26 {
            if j != t {
               score -= c[j] * (d - last[j].range(..d).rev().next().unwrap()) as i64;
            }
         }
         if score > mx {
            mx = score;
            tn = t;
         }
      }
      last[tn].insert(d);
      t.push(tn);
   }

   let mut rng = rand::thread_rng();
   loop {
      let elapsed = start.elapsed();
      if elapsed > time_limit {
         break;
      }
      let diff = elapsed.as_micros() as f64 / time_limit.as_micros() as f64;
      let temp: f64 = 1e9 * (-50.0 * diff).exp();
      let d = rng.gen_range(1, dn + 1);
      let mut q = rng.gen_range(0, 26);
      while t[d] == q {
         q = rng.gen_range(0, 26);
      }
      let p = t[d];
      let score = update(d, q, &s, &c, &mut t, &mut last);
      if score < 0 && rng.gen_range(0.0, 1.00) > (score as f64 / temp).exp() {
         t[d] = p;
         last[q].remove(&d);
         last[p].insert(d);
      }
   }
   for &t in t.iter().skip(1) {
      println!("{}", t + 1);
   }
}

fn update(
   d: usize,
   q: usize,
   s: &Vec<Vec<i64>>,
   c: &Vec<i64>,
   t: &mut Vec<usize>,
   last: &mut Vec<BTreeSet<usize>>,
) -> i64 {
   let p = t[d];
   let mut score = 0;
   score -= s[d][p];
   score += s[d][q];
   let f1 = last[p].range(..d).rev().next().unwrap();
   let b1 = last[p].range(d + 1..).next().unwrap();
   let f2 = last[q].range(..d).rev().next().unwrap();
   let b2 = last[q].range(d + 1..).next().unwrap();
   score -= c[p] * (d - f1) as i64 * (b1 - d) as i64;
   score += c[q] * (d - f2) as i64 * (b2 - d) as i64;
   t[d] = q;
   last[p].remove(&d);
   last[q].insert(d);
   score
}


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

int main()
{
        int n;
        int sum = 0;

        cin >> n;
        for ( int i = 0; i < n; i++ ) {
                int a;
                cin >> a;
                sum += a;
        }

        cout << sum << endl;

        return ( 0 );
}



Measured memory_bytes: 3124
#include <stdio.h>

#define MAX 20000000

int h, A[MAX];

void maxHeapify(int);

int main(){
  int i;
  scanf("%d",&h);
  for(i=1;i<=h;i++) scanf("%d",&A[i]);
  for(i=h/2;i>=1;i--) maxHeapify(i);

  for(i=1;i<=h;i++) printf(" %d",A[i]);
  printf("\n");



  return 0;
}

void maxHeapify(int i){
  int l, r, largest,swap;
  l = 2 * i;
  r = 2 * i + 1;

  /*左の子、自分、右の子で値が最大のノードを選ぶ*/
  if(l<=h && A[l]>A[i]) largest = l;
  else largest = i;
  if(r<=h && A[r]>A[largest]) largest = r;

  if(largest!=i){
    swap = A[i];
    A[i] = A[largest];
    A[largest] = swap;
    maxHeapify(largest);
  }
}



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

int main()
{
    int n;
    vector<int> r;
    while (scanf("%d",&n) != EOF)
    {
	int sum=0;
	for (int i=n; i<600; i+=n)
	{
	    sum+=i*i*n;
	}
	r.push_back(sum);
    }
    for (int i=0; i<r.size(); i++)
    {
	cout << r[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
 
using namespace std;

typedef long long ll;
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};

#define p(x) cout<<x<<endl;
 
ll i,j,k,l,ii,jj;
ll n,m;
ll x,y;
ll a[200005],b[200005];
ll ans=0;
ll v=-1,w;
ll num;

 
int main(){
    cin>>n;
	ll sum=0;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	a[0]=0;
	for(i=1;i<=n;i++){
		a[i]+=a[i-1];
	}
	sort(a,a+n+1);
	for(i=0;i<n;i++){
		if(a[i]==a[i+1]){
			num++;
		}else{
			num++;
			ans += num*(num-1)/2;
			num=0;
		}
	}
	num++;
	ans += num*(num-1)/2;

	p(ans);



	return 0;
}


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

int main(){
  int N,answer;
  cin >>N;
  for(int i=1;i<10;i++){
    if((i-1)*100+(i-1)*10+(i-1)<N && N<=i*100+i*10+i){
      answer=i*100+i*10+i;
      break;
    }
  }
  cout << answer;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a, b;
  int cnt=0, tmp=1;
    cin >> a >> b;
    for(int i=1; i<b; i+=a-1){
        cnt += 1;
    }
    //cout << tmp << endl;
    cout << cnt << endl;

}

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

int main() 
{
    int N;
    string S;
    cin >> N >> S;
    
    int ans = 0;
    char oldchar = '0';
    for (int i = 0; i < N; i++) {
        if (oldchar != S[i]) {
            ans++;
            oldchar = S[i];
        }
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string a, b;
	cin >> a >> b;
	if (a.size() > b.size()) {
		cout << "GREATER" << endl;
		return 0;
	}
	if (a.size() < b.size()) {
		cout << "LESS" << endl;
		return 0;
	}
	int n = a.size();
	rep(i, n) {
		if (int(a[i] - '0') > int(b[i] - '0')) {
			cout << "GREATER" << endl;
			return 0;
		}
		if (int(a[i] - '0') < int(b[i] - '0')) {
			cout << "LESS" << endl;
			return 0;
		}
	}
	cout << "EQUAL" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int MAX=1e5+5;



int main(){
	int X,K;
	cin>>X>>K;
	int R[MAX];
	R[0]=0;
	rep1(i,K)cin>>R[i];
	
	int l[MAX], r[MAX], ls[MAX], rs[MAX];
	l[0]=0;
	r[0]=X;
	ls[0]=0;
	rs[0]=X;
	rep1(i,K){
		if(i%2==1){
			int t=R[i]-R[i-1];
			if(t<=ls[i-1]){
				l[i]=l[i-1];
				r[i]=r[i-1];
				ls[i]=ls[i-1]-t;
				rs[i]=rs[i-1]-t;
			}
			else if(t<=rs[i-1]){
				l[i]=l[i-1]+t-ls[i-1];
				r[i]=r[i-1];
				ls[i]=0;
				rs[i]=rs[i-1]-t;
			}
			else{
				l[i]=r[i-1];
				r[i]=r[i-1];
				ls[i]=0;
				rs[i]=0;
			}
		}
		if(i%2==0){
			int t=R[i]-R[i-1];
			if(t<=X-rs[i-1]){
				l[i]=l[i-1];
				r[i]=r[i-1];
				ls[i]=ls[i-1]+t;
				rs[i]=rs[i-1]+t;
			}
			else if(t<=X-ls[i-1]){
				l[i]=l[i-1];
				r[i]=r[i-1]-t+(X-rs[i-1]);
				ls[i]=ls[i-1]+t;
				rs[i]=X;
			}
			else{
				l[i]=l[i-1];
				r[i]=l[i-1];
				ls[i]=X;
				rs[i]=X;
			}
		}
	}
	
	int Q;
	cin>>Q;
	rep(_,Q){
		int t, a;
		cin>>t>>a;
		int lb=0, ub=K+1;
		while(ub-lb>1){
			int mid=(lb+ub)/2;
			if(R[mid]<=t)lb=mid;
			else ub=mid;
		}
//		cout<<lb<<" ";
		
		int ans;
		
		if(lb%2==1){
			int dt=t-R[lb];
			if(a<l[lb]){
				ans=min(X, ls[lb]+dt);
			}
			else if(a<r[lb]){
				ans=min(X, ls[lb]+a-l[lb]+dt);
			}
			else{
				ans=min(X, rs[lb]+dt);
			}
		}
		if(lb%2==0){
			int dt=t-R[lb];
			if(a<l[lb]){
				ans=max(0, ls[lb]-dt);
			}
			else if(a<r[lb]){
				ans=max(0, ls[lb]+a-l[lb]-dt);
			}
			else{
				ans=max(0, rs[lb]-dt);
			}
		}
		
		cout<<ans<<endl;
	}
	
}

Measured memory_bytes: 3200
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif

int main_A() {
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    string S; cin >> S;

    int ans = 0;
    for (char c : S) {
        if (c == '+') ans++;
        else ans--;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().rstrip().split()))

total = 1
flg = True
for i in range(1,N):
    for j in range(i):
        if H[j] > H[i]:
            flg = False
            break
    if flg:
        total += 1
    else:
        flg = True
        
print(total)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;

ll n,m,q;
vector<ll>a,b,c,d;
ll ans;

void dfs(vector<ll> A){
    if(A.size()==n+1){
        ll now=0;
        for(ll i=0;i<q;i++){
            if(A[b[i]]-A[a[i]]==c[i]){
                now+=d[i];
            }
            ans=max(ans,now);
        }
        return;
    }
    A.push_back(A.back());
    while(A.back()<=m){
        dfs(A);
        A.back()++;
    }
}
int main() {
    cin >> n >> m >> q;
    a = b = c = d = vector<ll>(q);
    for(ll i=0;i<q;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    dfs(vector<ll>(1,1));
    cout << ans << endl;
}

Measured memory_bytes: 3612
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		h = scanner.nextInt();
		w = scanner.nextInt();
		n = scanner.nextInt();
		num = new Point[n + 1];
		map = new boolean[h][w];
		for (int i = 0; i < h; i++) {
			char[] chs = scanner.next().toCharArray();
			for (int j = 0; j < w; j++) {
				if (chs[j] == '.')
					continue;
				else if (chs[j] == 'X')
					map[i][j] = true;
				else if (chs[j] == 'S')
					num[0] = new Point(i, j);
				else
					num[chs[j] - '0'] = new Point(i, j);
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			ans += slove(num[i].y, num[i].x, num[i + 1].y, num[i + 1].x);
		}
		System.out.println(ans);
	}

	private int slove(int sy, int sx, int gy, int gx) {
		PriorityQueue<Point> pq = new PriorityQueue<Point>();
		int md = getMd(sy, sx, gy, gx);
		pq.offer(new Point(sy, sx, 0, md));
		boolean[][] tmpmap = new boolean[h][w];
		for (int i = 0; i < h; i++)
			tmpmap[i] = Arrays.copyOf(map[i], w);
		while (!pq.isEmpty()) {
			Point p = pq.poll();
			if (p.y == gy && p.x == gx) {
				return p.step;
			}
			if (tmpmap[p.y][p.x])
				continue;
			tmpmap[p.y][p.x] = true;
			for (int[] m : move) {
				int ny = p.y + m[0];
				int nx = p.x + m[1];
				if (!isOK(ny, nx))
					continue;
				
				int nstep = p.step + 1;
				int nmd = getMd(ny, nx, gy, gx) + nstep;
				pq.offer(new Point(ny, nx, nstep, nmd));

			}
		}
		return -1;
	}

	private boolean isOK(int ny, int nx) {
		if (0 <= ny && ny < h && 0 <= nx && nx < w)
			return true;
		return false;
	}

	private int getMd(int y1, int x1, int y2, int x2) {
		return Math.abs(y1 - y2) + Math.abs(x1 - x2);
	}

	int h, w, n;
	Point[] num;
	boolean[][] map;
	int[][] move = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

	class Point implements Comparable<Point> {
		int y, x, step, md;

		@Override
		public String toString() {
			return "Point [y=" + y + ", x=" + x + ", step=" + step + ", md="
					+ md + "]";
		}

		public Point(int y, int x, int step, int md) {
			super();
			this.y = y;
			this.x = x;
			this.step = step;
			this.md = md;
		}

		public Point(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public int compareTo(Point o) {
			if (md == o.md)
				return o.step - this.step;
			return this.md - o.md;
		}

	}
}

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

int main() {
  int H,W; cin >>H >>W; 
  
  //入れる
  vector<vector<char>> mass(H,vector<char>(W));
  for(int i=0;i<H;i++)
  {
    for(int j=0;j<W;j++)
    {
      cin >>mass.at(i).at(j);
    }    
  }

  //削る
  //縦軸.横の数だけ縦を
  for(int i=0;i<W;i++)
  {
    int count =0;
    for(int j=0;j<H;j++)
    {
    if(mass.at(j).at(i)=='.')count++;
      //xに変える
      if(count==H){
        for(int k=0;k<H;k++)
        {
        mass.at(k).at(i)='x';
        }
      }
    }
  }
  
  //横
  for(int i=0;i<H;i++)
  {
    int count =0;
    for(int j=0;j<W;j++)
    {
    if(mass.at(i).at(j)!='#')count++;
      //xに変える
      if(count==W){
        for(int k=0;k<W;k++)
        {
        mass.at(i).at(k)='x';
        }
      }
    }
  }
  
  for(int i=0;i<H;i++)
  {
    int count=0;
    for(int j=0;j<W;j++)
    {
      if(mass.at(i).at(j)!='x')cout <<mass.at(i).at(j);
      else count++;
      if(j==W-1&&count<W-1)cout <<endl;
    }    
  }
  
}


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

int A, B, C, X, Y;

int main() {
    cin >> A >> B >> C >> X >> Y;
    int ans = 0;
    int hoge = (A+B < 2*C) ? A+B : 2*C;
    while(X != 0 && Y != 0) {
        X--; Y--;
        ans += hoge;
    }
    if (Y && B < 2*C) ans += Y*B;
    else if (X && A < 2*C) ans += X*A;
    else {
        hoge = X > Y ?  X : Y;
        ans += hoge*2*C;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# coding=utf-8

import sys

s = sys.stdin.readline().strip().split("T")
x, y = sys.stdin.readline().strip().split(" ")
x = int(x)
y = int(y)
move_all = [len(_s) for _s in s]
pos_x = set([move_all[0]])
pos_y = set([0])
move_x = move_all[2::2] or None
move_y = move_all[1::2] or None
if move_x:
    for move in move_x:
        pos_x = {_x + move for _x in pos_x} | {_x - move for _x in pos_x}
if move_y:
    for move in move_y:
        pos_y = {_y + move for _y in pos_y} | {_y - move for _y in pos_y}
if x in pos_x and y in pos_y:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 4964
fn main() {
    let arg: String = read();

    let mut old_c = ' ';
    let mut new_c;

    for c in arg.chars().enumerate() {
        new_c = c.1;
        if old_c == new_c {
            println!("Bad");
            return;
        }
        old_c = c.1;
    }
    println!("Good");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}


Measured memory_bytes: 4352