akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
	int a,b,c,temp,s=0,x,y,i[100000],j[100000];
	cin>>a;
	for(b=0;b<a;b++){
		j[b]=0;
	}
	for(b=0;b<a;b++){
		cin>>i[b];
		if(i[b]==b+1){
			j[b]=1;
		}
	}
	for(y=1;y<2;){
		for(b=0;b<a;b++){
		    if(j[b]==1){
		    	s++;
		    	if(j[b-1]==1){
		    		temp=i[b-1];
				    i[b-1]=i[b];
				    i[b]=temp;
				    j[b]=0;
				    j[b-1]=0;
				}else{
					if(j[b+1]==1){
				    j[b]=0;
				    j[b+1]=0;
				}
					if(i[b+1]!=b+1){
			    	    temp=i[b+1];
	    	    	    i[b+1]=i[b];
    			        i[b]=temp;
    			        if(i[b]!=b+1){
    			        	j[b]=0;
						}
			        }else{
				        temp=i[b-1];
				        i[b-1]=i[b];
				        i[b]=temp;
				        if(i[b]!=b+1){
    			        	j[b]=0;
						}
			        }
				}
			}
		}
	    x=0;
	    for(b=0;b<a;b++){
	    	if(j[b]==1){
	    		continue;
			}
		}
		cout<<s;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  long x = 0, X = 0, ans = Long.MAX_VALUE;
  long[] arr = new long[n];
  for (int i = 0; i < n; i++) {
    arr[i] = sc.nextInt();
    X += arr[i];
  }
  for (int i = 0; i < n; i++) {
    x += arr[i];
    if (i + 1 < n) {
      ans = Math.min(ans, Math.abs(X - 2 * x));
    }
  }
  System.out.println(ans);
  }
}


Measured memory_bytes: 83148
n, q = map(int, input().split())
s = input()
counts = [0 for i in range(n)]
count = 0

for i in range(n):
    if s[i-1:i+1] == 'AC':
        count+=1
    counts[i] = count


for i in range(q):
    l, r = map(int,input().split())
    print (counts[r-1] - counts[l-1])


Measured memory_bytes: 6184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	// your code goes here
	ll n,testCase;
	//cin>>testCase;
	string s,t,u;
	int a,b;
	cin>>s>>t;
	cin>>a>>b;
	cin>>u;
	if(u==s)
	{
		a--;
	}
	else if(u==t)
	{
		b--;
	}
	cout<<a<<" "<<b<<endl;
	return 0;
}

/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	// your code goes here
	ll n,testCase;
	cin>>testCase;
	while(testCase--)
	{
		vector<ll>v;
		cin>>n;
		ll x=n;
		ll cnt=0;
    ll ans,tmp,tmp1;
		while(1)
		{
			  ans=n/10;
	     	tmp=n%10;
	     	tmp1=tmp+ans;
	     	n=tmp1;
        cnt+=(ans*10);
        //cout<<" ans "<<ans<<" tmp "<<tmp<<" tmp1 "<<tmp1<<endl;
	     	if(n<10)
	     	{
	     		break;
	     	}
		}
    //cout<<cnt<<endl;
		cout<<(cnt+tmp1)<<endl;

	}
	return 0;
}
*/


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#include <bits/stdc++.h>
#define rep(i ,n) for(int i=0;i<(int)(n);++i)
#define repr(i ,n) for(int i=n;i>(int)(n);--i)
#define rep1(i ,n) for(int i=1;i<=(int)(n);++i)
#define ALL(a) a.begin(), a.end()
#define RSORT(a) sort(ALL(a),greater<>())
#define SORT(a) sort(ALL(a))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define PRINT(x) printf("%d\n",(x));
#define ENDL printf("\n");
using namespace std;
typedef long long int i64;
typedef unsigned long long u64;
template<class T> using V = vector<T>;
using I = int;
using VI = V<I>;
const int INF = 2e9;
const i64 MOD = 1e9 + 7;

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;}

signed main(){
    int n; cin >> n;
    VI s(n);
    rep(i ,n) cin >> s[i];
    int q; cin >> q;
    VI t(q);
    rep(i ,q) cin >> t[i];

    int counter = 0;
    rep(i ,q){
        if(binary_search(ALL(s) , t[i])) ++counter;
    }
    PRINT(counter);
}


Measured memory_bytes: 3412
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int m1 = sc.nextInt();
        int d1 = sc.nextInt();
        int m2 = sc.nextInt();
        if(m1 == m2){
            System.out.println("0");
        } else {
            System.out.println("1");
        }
    }
}


Measured memory_bytes: 23252
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int a=s.nextInt();
		int b=s.nextInt();
		int c=s.nextInt();
		s.close();
		int d=(int)Math.floor(b/a);
		System.out.println(Math.min(c, d));
	}
}


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

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; const ll MOD = 1000000007;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

//---------------------------------------------------------------------------------------------------
void _main() {
    ll N; string S; cin >> N >> S;
    ll cnt = 0;
    rep(i, 0, 1000) {
        ll c[3] = {i/100, (i / 10) % 10, i % 10};
        ll f = 0;
        rep(j, 0, N) {
            if(S[j] == ('0' + c[f])) f++;
            if (f ==3 ) break;
        }
        if (f == 3) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int A,B,X;
    scanf("%d%d%d",&A,&B,&X);
    if(A+B>=X && X>=A){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }
}

Measured memory_bytes: 256
fun main() {
    val builder = StringBuilder()

    val n = readInputLine().toInt()

    val aArr = readInputLine().split(" ").map { it.toInt() }.sorted().toIntArray()

    val allNumCnt = mutableMapOf<Int, Int>()

    for (a in aArr) {
        allNumCnt[a] = (allNumCnt[a] ?: 0) + 1
    }

    val set = mutableSetOf<Int>()

    var ans = 0

    for (a in aArr) {
        if (allNumCnt[a] == 1) {
            var ok = true

            for (i in 1..a) {
                if (i * i > a) {
                    break
                }
                if (a % i != 0) {
                    continue
                }
                if (set.contains(i) || set.contains(a / i)) {
                    ok = false
                    break
                }
            }

            if (ok) {
                ans++
            }
        }

        set.add(a)
    }

    builder.appendln(ans)

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, d[101010];
void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> d[i];
	}
	sort(d,d+n);
	
	cout << d[n/2]-d[n/2-1] << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static String z;
    static long sum=0;


    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        String word = s.next();
        z="";
        int n = word.length()-1;
        for(int i=0;i<word.length();i++){
            if(i!=word.length()-1)z+=word.charAt(i)+" ";
            else z+=word.charAt(i);
        }

        solve(0,n,"");


        System.out.println(sum);

    }

    public static void solve(int start, int n,String acc){
        if(start==n){
            String res="";
            for(int i=0,j=0;i<z.length();i++){
                if(z.charAt(i)==' '){
                    if(acc.charAt(j++)=='+')res+='+';
                }
                else res+=z.charAt(i);
            }

            String ac = "";
            for(int i=0;i<res.length();i++){
                if(res.charAt(i)=='+'){
                    sum+= Long.parseLong(ac);
                    ac="";
                }
                else {
                    ac+=res.charAt(i);
                }
            }
            sum+= Long.parseLong(ac);

        }
        
        else{
            solve(start+1,n,acc+" ");
            solve(start+1,n,acc+"+");
        }
    }

}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

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

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

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 28372
#include<iostream>
using namespace std;
int selectionSort(int a[],int N)
{
    int sw=0;
    int temp;

    for(int j=0;j<N-1;j++)//??????????¬???°
    {
        int k=j;
        for(int i=j+1;i<N;i++){
            if(a[i]<a[k]){
                k=i;

            }

        }
        temp=a[j];
        a[j]=a[k];
        a[k]=temp;
        if(j!=k)
            sw++;

    }
    return sw;
}








int main()
{
    int N,sw;
    cin>>N;
    int a[100];
    for(int i=0;i<N;i++)
        cin>>a[i];
    sw=selectionSort(a,N);
    for(int i=0;i<N;i++)
    {
        if(i)
            cout<<" ";
        cout<<a[i];
    }
    cout<<endl;
    cout<<sw<<endl;
}

Measured memory_bytes: 3108
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int coin[21];
    int amount[50001];
    
    
    
    for(int i=0;i<m;i++)
    {
        cin>>coin[i];
    }
    
    for(int i=0;i<n+1;i++)
    {
        amount[i]=99999999;
    }
    amount[0]=0;
    
    for(int i=0;i<m+1;i++)
    {
        for(int j=coin[i];j<n+1;j++)
        {
            amount[j]=min(amount[j],amount[j-coin[i]]+1);
        }
    }
    cout<<amount[n]<<endl;
}

Measured memory_bytes: 3252
#include<bits/stdc++.h>
using namespace std;
int box[100002];
int main(void){
	int n,m;
	int x,y;
	int i;
	int cnt;
	cin>>n>>m;
	for(i=0;i<=n+1;i++)	box[i]=0;
	for(i=0;i<m;i++){
		cin>>x>>y;
		box[x]++;
		box[y+1]--;
	}
	for(i=0;i<=n;i++)	if(i>0)	box[i]+=box[i-1];
	for(i=0;i<=n;i++)	if(m==box[i])	cnt++;
	cout<<cnt<<endl;
	return 0;
}
	
	
	

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}
/*
typedef __int128_t Int;
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
  if (s) {
	__uint128_t tmp = value < 0 ? -value : value;
	char buffer[128];
	char *d = std::end(buffer);
	do {
	  --d;
	  *d = "0123456789"[tmp % 10];
	  tmp /= 10;
	} while (tmp != 0);
	if (value < 0) {
	  --d;
	  *d = '-';
	}
	int len = std::end(buffer) - d;
	if (dest.rdbuf()->sputn(d, len) != len) {
	  dest.setstate(std::ios_base::badbit);
	}
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
	if ('0' <= s[i] && s[i] <= '9')
	  ret = 10 * ret + s[i] - '0';
  return ret;
}
*/

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
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 (a > b) {
		a = b;
		return true;
	}
	return false;
}

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N; cin >> N;
	if (N == 3) {
		cout << "2 5 63" << endl;
	}
	else {
		vector<int>v;
		if (N % 2 == 0) {
			v = { 2,10,3,9,4,8,6,12 };
		}
		else {
			v = { 6,2,10,3,9,4,8,12 };
		}
		rep(i, 0, N) {
			cout << v[i] << (i == N - 1 ? '\n' : ' ');
			v.eb(v[i] + 12);
		}

	}

	return 0;
}


Measured memory_bytes: 768
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;
ll const MAX_N = 510000;
ll const MOD = 1000000007;

int main() {
    string S_in, T;
    cin >> S_in >> T;

    vector<ll> idx;

    rep(i, S_in.length() - T.length() + 1) {
        bool is_s = true;
        rep(j, T.length()) {
            if (S_in[i + j] == '?') continue;

            if (S_in[i + j] != T[j]) {
                is_s = false;
                break;
            }
        }
        if (is_s) {
            idx.push_back(i);
        }
    }

    if (idx.size() == 0) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }

    rep(i, S_in.length()) {
        if (S_in[i] == '?') S_in[i] = 'a';
    }

    vector<string> S_cand;
    repv(idx) {
        ll i = *it;
        string S = S_in;

        rep(j, T.length()) { S[i + j] = T[j]; }
        S_cand.push_back(S);
    }

    sort(S_cand.begin(), S_cand.end());

    cout << S_cand[0] << endl;

    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

struct SegmTree {
  int n;
  vector<int> a, tree, lazy, where;
  SegmTree(const vector<int> a_) :
    n(a_.size()), a(a_), tree(4 * n), lazy(4 * n), where(4 * n) {
      Build(0, 0, n - 1);
  }
  void Recalc(int node) {
    if (tree[2 * node + 1] < tree[2 * node + 2]) {
      tree[node] = tree[2 * node + 1];
      where[node] = where[2 * node + 1];
    } else {
      tree[node] = tree[2 * node + 2];
      where[node] = where[2 * node + 2];
    }
  }
  void Build(int node, int left, int right) {
    if (left == right) {
      tree[node] = a[left];
      where[node] = left;
      return;
    }
    int mid = left + (right - left) / 2;
    Build(2 * node + 1, left, mid);
    Build(2 * node + 2, mid + 1, right);
    Recalc(node);
  }
  inline void Add(int node, int val) {
    tree[node] += val;
    lazy[node] += val;
  }
  inline void Propagate(int node) {
    if (lazy[node] == 0) return;
    Add(2 * node + 1, lazy[node]);
    Add(2 * node + 2, lazy[node]);
    lazy[node] = 0;
  }
  void Update(int node, int left, int right, int pos) {
    if (pos >= right) {
      Add(node, 1);
      return;
    }
    Propagate(node);
    int mid = left + (right - left) / 2;
    Update(2 * node + 1, left, mid, pos);
    if (mid < pos)
      Update(2 * node + 2, mid + 1, right, pos);
    Recalc(node);  
  }
  pair<int, int> Query(int node, int left, int right, int pos) {
    if (left >= pos) {
      return make_pair(tree[node], where[node]); 
    }
    Propagate(node);
    int mid = left + (right - left) / 2;
    pair<int, int> ret = {(int)2e9, -1};
    if (pos <= mid)
      ret = Query(2 * node + 1, left, mid, pos);
    ret = min(ret, Query(2 * node + 2, mid + 1, right, pos));
    return ret;
  }
  pair<int, int> Query(int pos) {
    return Query(0, 0, n - 1, pos);
  }
  void Update(int pos) {
    if (pos >= 0)
      Update(0, 0, n - 1, pos);
  }
};

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

  int n; cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  auto b = a;
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  SegmTree st(b);
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int pos = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    pair<int, int> val = st.Query(pos);
    ans += val.first - a[i]; 
    st.Update(val.second - 1);
  }
  cout << ans << endl;


  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

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

using namespace std;
using ll=long long;
int main(){
    ll h;
    cin >> h;
    ll ans;
    vector<ll> b(60);
    ll beg=1;
    ll cnt;
    for(int i=0;i<60;i++){
        b[i]=beg;
        beg*=2;
        //cout << beg << endl;
    }
    ll beg2=1;
    for(int i=0;i<60;i++){
        if(beg2>h){
            ans=i;
            break;
        }
        beg2*=2;
    }
    ll sum=0;
    for(int i=0;i<ans;i++){
        sum+=b[i];
    }
   cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

using namespace std;

int main(){

    int d, n;

    cin >> d;
    cin >> n;

    int t = 1;

    for(int i=0; i<d; i++){
        t *= 100;
    }

    int x = t * n;
    int c;
    int z = x;
    for(int i=0; i<d; i++)
        z /= 100;

    if(z % 100 == 0)
        x += t;
    cout << x << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-bin(s).count('1'))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll k,t;
    cin >> k >> t;
    priority_queue<pair<ll,ll>> pq;
    for(i = 0;i < t;++i){
        ll a;
        cin >> a;
        pq.emplace(a, i);
    }
    auto x = pq.top();
    ll num = x.first;
    ll tmp = x.second;
    --num;
    pq.pop();
    if(num != 0){
        pq.emplace(num, tmp);
    }
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        if(tmp != x.second){
            --x.first;
            tmp = x.second;
            if(x.first != 0) pq.emplace(x);
        }else{
            if(pq.empty()){
                cout << x.first << endl;
                return 0;
            }else{
                auto y = pq.top();
                pq.pop();
                tmp = y.second;
                --y.first;
                pq.emplace(x);
                if(y.first != 0) pq.emplace(y);
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
//
//AISing 2020
//A
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    int l,r,d;
    cin >> l >> r >> d;

    int ans=0;
    FOR(i, l, r){
        if (i%d==0) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3584
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)
    val a = sc.nextLong()
    val b = sc.nextLong()
    val c = sc.nextLong()
    println(if (a + b < c && 4L * a * b < (c - a - b) * (c - a - b)) "Yes" else "No")
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 31400
#include <bits/stdc++.h>
using namespace std;
int main(){
  cout << fixed << setprecision(20);
  int N;
  cin >> N;
  vector<double> v(N);
  for (int i = 0; i < N; i++){
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  stack<double> S;
  for (int i = N - 1; i >= 0; i--){
    S.push(v[i]);
  }
  while (S.size() > 1){
    double A = S.top();
    S.pop();
    double B = S.top();
    S.pop();
    S.push((A + B) / 2);
  }
  cout << S.top() << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
#include <string>
#include <map>
#include <set>
#include <list>
#include <stdio.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;
////////////////////////////
#define pll pair<ll,ll>
#define mkp make_pair

ll N,A[101010],B[101010];

ll i,j,k;

vector<pll> vAB;
bool ck[101010];
ll ans=0;

int main(){
    scanf("%lld",&N);
    //ll mina=LLONG_MAX,minb=0,minc=-1;
    fornum(i,0,N){
        scanf("%lld%lld",&A[i],&B[i]);
    }

    fornum(i,0,N){
        vAB.push_back(mkp(A[i],i));
        vAB.push_back(mkp(B[i],i));
    }
    sort(vAB.begin(),vAB.end());
    
    ll rslt=0;
    fornum(i,0,N)
        ans+=A[i];
    fornum(i,0,N)
        rslt+=B[i];
    if(rslt<ans)ans=rslt;

    bool fg=false;
    rslt=0;
    fornum(i,0,N){
        auto s=vAB[i];
        rslt+=s.first;
        if(ck[s.second])
            fg=true;
        else
            ck[s.second]=true;
    }
    if(fg){
        if(rslt<ans)ans=rslt;
    }else{
        ll Nrslt=rslt;
        fornum(i,0,N){
            auto s=vAB[i];
            if(vAB[N].second!=s.second){
                rslt=Nrslt-s.first+vAB[N].first;
            }else{
                rslt=Nrslt-s.first+vAB[N+1].first;
            }
            if(rslt<ans)ans=rslt;
        }
    }
    

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

    return 0;
}





Measured memory_bytes: 7920
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n;
  long long sum,sa;
  sum = 0;
  sa = 0;
  cin >> n;
  vector<long long> a(n);
  for(long long i=0;i<n;i++){
    cin >> a.at(i);
    sa += a.at(i);
  }
  for(long long i=0;i<n;i++){
    sa -= a.at(i);
    sum += sa % 1000000007 * a.at(i);
    sum %= 1000000007;
  }
  cout << sum << endl;
}



Measured memory_bytes: 4788
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

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 <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

signed main() {
  ll a;
  cin >> a;
  string s;
  cin >> s;
  if (a >= 3200) {
    COUT(s);
  } else {
    COUT("red");
  }
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct pos { double x, y; };
double dir(pos p1, pos p2) { return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2)); }
int main() {
    pos p[3];
    for (int i = 0; i < 3; i++) scanf("%lf %lf%*c", &p[i].x, &p[i].y);
    double a = dir(p[0], p[1]),
        b = dir(p[0], p[2]),
        c = dir(p[1], p[2]),
        s = (a + b + c) / 2.0,
        S = sqrt(s * (s - a) * (s - b) * (s - c)),
        r = 2 * S / (a + b + c),
        D = max(a, max(b, c));
    printf("%.10f\n", r * D / (2 * r + D));
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repr(i,a,n) for(int i=a;i>n;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int a, b, c, x;
  cin >> a >> b >> c >> x;
  int count = 0;
  rep(i,0,a+1){
    rep(j,0,b+1){
      rep(k,0,c+1){
        if(500*i + 100*j + 50*k == x) count++;
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
import collections
N = int(input())
a = list(map(int,input().split()))
count = []
ans = 0
for i in range(N):
  count.append(a[i]-1)
  count.append(a[i])
  count.append(a[i]+1)
ans = max(collections.Counter(count).values())
print(ans)

Measured memory_bytes: 27360
N = int(input())
A = list(map(int, input().split()))
sort_A = sorted(A, reverse=True)
Ans = 0

loop = N // 2
for i in range(loop):
  Ans = Ans + (sort_A[i] * 2) 

Ans = Ans - sort_A[0]

if N % 2 == 1:
  Ans = Ans + sort_A[(N-1) // 2]

print(Ans)

Measured memory_bytes: 31492
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

int main() {
  //
  ll h, w, a, b;
  cin >> h >> w >> a >> b;
  rep(i, h) {
    rep(j, w) { cout << ((i < b) ^ (j < a)); }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 1280
n, x = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
ans = 0
if a[0] > x:
    ans += a[0] - x
    a[0] = x
for i in range(1,len(a)):
    if a[i-1] + a[i] > x:
        ans += a[i-1] + a[i] - x
        a[i] = x - a[i-1]
print(ans)

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int [N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		long total = 0;
		int cen = (N-1)/2;
		if (N == 2)
			total = a[1] - a[0];
		
		else if (N % 2 == 0) {
			total += a[cen+1] - a[cen];
			for (int i = 0; i < cen; i++) {
				total += 2* (a[N-1-i] - a[i]);
			}
		}
		else {
		int total1 = 0;
		int total2 = 0;
		for ( int i = 0; i < cen-1; i++) {
			total += 2 * (a[N-1-i] - a[i]);
		}
		total1 += a[cen+1] + a[cen+1] - a[cen] - a[cen-1];
		total2 += a[cen] + a[cen+1] - a[cen-1] - a[cen-1];
		total += Math.max(total1, total2);
		}
		
		System.out.println(total);
		
	}
}	


Measured memory_bytes: 52148
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int h, w;
bool graph[1004][1004];
int dp[1004][1004];

int main() {
	cin>>h>>w;
	char c;
	for(int i = 1;i<=h;i++)
		for(int j = 1;j<=w;j++){
			cin>>c;
			graph[i][j] = c=='#';
		}
	memset(dp,0,sizeof(dp));
	dp[1][1] = 1;
	for(int i = 1;i<=h;i++)
		for(int j = 1;j<=w;j++){
			if(dp[i][j]){
				if(!graph[i+1][j])	dp[i+1][j]  = (dp[i+1][j]+dp[i][j])%mod;
				if(!graph[i][j+1])	dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod;
			}
		}
	cout<<dp[h][w];
	return 0;
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N;
  cin>>N;
  vector<int> A(N);
  for(int &i:A)cin>>i;
  int n=201,m=-1,l=0,a=1000,b=0;
  for(int i=0;i<N-1;i++){
    if(A[i]<A[i+1]){
      if(m==-1){
        b=a/A[i];
        a%=A[i];
      }
      m=1;
    }else{
      if(m==1){
        a+=b*A[i];
        b=0;
      }
      m=-1;
    }
  }
  cout<<a+b*A[N-1]<<endl;
}

Measured memory_bytes: 3632
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		List<Integer> students = new ArrayList<>();
		for(int i = 0; i < num; i++) {
			students.add(0);
		}

		for(int i = 1; i <= num; i++) {
			students.set(sc.nextInt() - 1, i);
		}

		for (Integer s : students) {
			System.out.print(s + " ");
		}

	}
}

Measured memory_bytes: 65108
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    string sa,sb,sc;cin>>sa>>sb>>sc;
    int na=sa.length(),nb=sb.length(),nc=sc.length();
    int ia=0,ib=0,ic=0;
    char now=sa[ia];
    na--;
    ia++;
    while(1){
        if(now=='a'){
            if(!na){
                cout<<"A"<<endl;
                return 0;
            }
            now=sa[ia];
            na--;
            ia++;
        }
        else if(now=='b'){
            if(!nb){
                cout<<"B"<<endl;
                return 0;
            }
            now=sb[ib];
            nb--;
            ib++;
        }
        else if(now=='c'){
            if(!nc){
                cout<<"C"<<endl;
                return 0;
            }
            now=sc[ic];
            nc--;
            ic++;
        }
    }
   /* if(!na)
        cout<<"A"<<endl;
    else if(!nb)
        cout<<"B"<<endl;
    else
        cout<<"C"<<endl;*/
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 256
#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 debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

int main(){
    int k, t;
    vector< pair<int, int> > v;
    cin >> k >> t;
    rep(i,t){
        int inp;
        cin >> inp;
        v.emplace_back(make_pair(inp,i));
    }
    int b = -1;
    while(not v.empty()){
        sort(all(v), greater<pair<int,int>>());
        if(v[1].first== 0) break;
        if(b == v[0].second){
            v[1].first--;
            b = v[1].second;
        }else{
            v[0].first--;
            b = v[0].second;
        }
    }
    if(v[0].second != b) v[0].first--;
    if(v[0].first== -1) v[0].first= 0;
    cout << v[0].first<< endl;
}


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

from collections import Counter
C=Counter(A)
ANS=0
for i in C.values():
    ANS+=i*(i-1)//2

for a in A:
    k=C[a]

    print(ANS-(k*(k-1)//2)+((k-1)*(k-2)//2))


Measured memory_bytes: 25716
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	X := make([]int, M)
	for i := range X {
		fmt.Scan(&X[i])
	}
	if M < N {
		fmt.Println(0)
		return
	}

	sort.Ints(X)
	Sa := make([]int, M)
	for i := range X {
		if i == 0 {
			continue
		}
		Sa[i] = X[i] - X[i-1]
	}
	sort.Ints(Sa)
	ans := 0
	for _, po := range Sa[:M-N+1] {
		ans += po
	}
	fmt.Println(ans)

}


Measured memory_bytes: 5504
ans = {"AC"=> 0, "WA"=> 0, "TLE"=> 0, "RE"=> 0}
n = gets.chomp.to_i
n.times do
    s = gets.chomp
    ans[s] += 1
end

ans.each do |key, count|
    puts key + " x " + count.to_s
end

Measured memory_bytes: 14220
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string s;
  cin>>s;
  int n=s.size();
  int ans=0;
  map<char,char> r;
  r['[']=']';
  r[']']='[';
  r['(']=')';
  r[')']='(';
  r['{']='}';
  r['}']='{';
  r['i']='i';
  r['w']='w';
  for(int b=0;b<(1<<n);b++){
    string t;
    for(int i=0;i<n;i++) if((b>>i)&1) t+=s[i];
    if(t.find("iwi")==string::npos) continue;
    int k=t.size();
    if(k%2==0) continue;
    if(t[k/2-1]!='i'||t[k/2]!='w'||t[k/2+1]!='i') continue;
    bool f=1;
    for(int i=0;i<k/2;i++) f&=t[i]==r[t[k-1-i]];
    if(f) ans=max(ans,k);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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

    vi a(n);
    rep(i, n) {
        if(s[i] == 'R') a[i] = 0;
        if(s[i] == 'G') a[i] = 1;
        if(s[i] == 'B') a[i] = 2;
    } 
    vll cnt(3);
    rep(i, n) cnt[a[i]]++;
    ll ans = 1;
    rep(i, 3) ans *= cnt[i];
    rep(j, n)rep(i, j) {
        int k = j + (j - i);
        if(k < n) {
            if(a[i] == a[j]) continue;
            if(a[i] == a[k]) continue;
            if(a[j] == a[k]) continue;
            ans--;
        }
    }

    cout << ans << endl;
    
    return 0;
}


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

long long a[200001],b[200001];
int n;
long long s=0,ans=0,t;
	
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	for (int i=n;i>=1;i--)
	{
		a[i]+=s;
		if (a[i]==0) continue;
		t=(a[i]-1)%b[i]+1;
		s+=b[i]-t;
		ans+=b[i]-t;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
from collections import defaultdict

n, m = map(int, input().split())
A = list(map(int, input().split()))

accum = [0] * (n + 1)

for i in range(n):
  accum[i + 1] = accum[i] + A[i]
  
box = defaultdict(int)

for i in accum:
  box[i % m] += 1
  
ans = 0
for v in box.values():
  ans += v * (v - 1) // 2
  
print(ans)

Measured memory_bytes: 16796
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        final int mod = 998244353;
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final int k = sc.nextInt();
        final int[][] data = new int[k][2];
        for (int i = 0; i < k; i++) {
            data[i][0] = sc.nextInt();
            data[i][1] = sc.nextInt() + 1;
        }
        final long[] dp = new long[n];
        dp[0] = 1;
        dp[1] = -1;
        for (int i = 0; i < n; i++) {
            if (i != 0) { 
                dp[i] = (dp[i] + dp[i - 1]) % mod;
            }
            for (int j = 0; j < k; j++) {
                final int l = data[j][0] + i;
                final int r = data[j][1] + i;
                if (l < n) { 
                    dp[l] = (dp[l] + dp[i]) % mod;
                }
                if (r < n) { 
                    dp[r] = (dp[r] - dp[i] + mod) % mod;
                }
            }
        }
        System.out.println(dp[n - 1]);
    }
}


Measured memory_bytes: 38696
#include <iostream>
#include<cmath>
#include<vector>
#include<map>
#include<sstream>
#include<deque>
#include<iomanip>
#include<algorithm>
#include<set>
#include<queue>
#include<bitset>
#include<stack>
#include<unordered_set>
using namespace std;
//	int x=atoi(s.c_str()); s_to_in;
int dx[] = { -1,0,0,1 };
int dy[] = { 0,1,-1 ,0};
#define endl '\n'
long long mo = 1e9;
const long double P = 3.141592653589793238L;
void trust_yourself()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
long long gcd(long long x, long long y)
{
	if (x == 0)
		return y;
	return gcd(y%x, x);
}
long long fast_power(long long x, long long y, long long mo)
{
	long long p = 1;
	while (y)
	{
		if (y & 1)
			p = (p*x) % mo;
		y = (y >> 1); //y/=2
		x = (x*x) % mo;
	}

	return p;
}
long long convert_to_num(string x) {
	long long  num = 0;
	for (int i = 0; i < x.size(); i++) {
		num *= 2;
		num += x[i] - '0';
	}
	return num;
}

long long com(long long n, long long r) {
	long long p = 1, p1 = 1;
	for (long long i = r + 1; i <= n; i++) {
		p = p * i;
		p /= p1;
		p1++;
	}
	return p;
}



int main()
{
	trust_yourself();
	//freopen("hussien.in", "r", stdin);
	
	int n; long long s = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (i % 3 != 0 && i % 5 != 0)
			s += i;
	}
	cout << s;
	
	return 0;

}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
 
typedef long long int ll; 
typedef long double ld; 
 
#define MAX 200005
#define endl endl


int main()
{
	
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	string s;
	cin>>s;
	
	ll st = 0;
	ll ed = -1+s.size();
	ll ans = 0;
	while(st<=ed){
		while(st<s.size() && s[st]=='R'){
			st++;
		}
		while(ed>-1 && s[ed] == 'W'){
			ed--;
		}
		//cout<<st<<" "<<ed<<endl;
		if(st<=ed){
			swap(s[st], s[ed]);
			ans++;
			st++;
			ed--;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3732
#include <stdio.h>
#define MAX 100000

void Preorder(int);
void Inorder(int);
void Postorder(int);

int n;
int i;

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

struct Node T[MAX];

int main(void){
  int j,left,right,c[MAX];
  int id[MAX],p,s,deg[MAX],dep,h;
  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    T[i].p = -1;
    T[i].s = -1;
    T[i].l = -1;
    T[i].r = -1;
  }
  
  for(i = 0 ; i < n ; i++){
    scanf("%d",&id[i]);
  
    for(j = 0 ; j < 2 ; j++){
      scanf("%d",&c[j]);
      
      if(j == 0){
	left = c[j];
	T[id[i]].l = c[j];
	T[c[j]].p = id[i];
      }
      else {
	right = c[j];
	T[id[i]].r = c[j];
	T[c[j]].p = id[i];
      }
    }
  }

  for(i = 0 ; i < n ; i++){
    if(T[i].p == -1) break;
  }
  
  printf("Preorder\n");
  Preorder(i);
 
  printf("\nInorder\n");
  Inorder(i);
 
  printf("\nPostorder\n");
  Postorder(i);
  printf("\n");
  
  return 0;
}

void Preorder(int u){

  printf(" %d",u);
 
  if(T[u].l != -1){
    Preorder(T[u].l);
  }
  if(T[u].r != -1){
    Preorder(T[u].r);
  }
}

void Inorder(int u){

  if(T[u].l != -1){
    Inorder(T[u].l);
  }
  printf(" %d",u);

  if(T[u].r != -1){
    Inorder(T[u].r);
  }
}

void Postorder(int u){
   
  if(T[u].l != -1){
    Postorder(T[u].l);
  }
  if(T[u].r != -1){
    Postorder(T[u].r);
  }
  printf(" %d",u);
  
}

Measured memory_bytes: 0
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
// *max_element(all(d))
class UnionFind{
  private:
    vector<int>par;
  public:
    UnionFind(int n):par(n,-1){}
    int root(int x){
      if(par[x] < 0)return x;
      return par[x] = root(par[x]);
    }
    bool unite(int x,int y){
      x = root(x); y = root(y);
      if (x == y) return false;
      if (par[x] > par[y]) swap(x, y);
      par[x] += par[y];
      par[y] = x;
      return true;
    }
    bool same(int x,int y){
      return root(x) == root(y);
    }
    int size(int x) {
      return -par[root(x)];
    }
};
int solve(){
  int n,m;
  cin >> n >> m;
  vector<pair<int,int>>G(m);
  vector<int>cnt(n,1);
  vector<bool>red(n,false);
  red[0] = true;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    G[i].first = a;
    G[i].second = b;
  }
  rep(i,m){
    int a = G[i].first,b = G[i].second;
    cnt[a]--;
    cnt[b]++;
    if(red[a] && cnt[a] >= 1)red[b] = true;
    else if(red[a] && cnt[a] <= 0){
      red[a] = false;
      red[b] = true;
    }
  }
  int ans = 0;
  rep(i,n)if(red[i] && cnt[i])ans++;
  cout << ans << endl;
  return 0; 
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];
  int odd=0, num4=0; // 奇数と4の倍数の個数
  for (int i=0; i<N; i++) {
    if (a[i]%2!=0) odd++;
    else if (a[i]%4==0) num4++;
  }
  if (odd+num4==N) {
    if (odd<=num4+1) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  else {
    if (odd<=num4) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> x(N), y(N);
  vector<char> c(N);
  for (int i = 0; i < N; i++){
    cin >> x[i] >> y[i] >> c[i];
    x[i]++;
    y[i]++;
    if (c[i] == 'W'){
      y[i] += K;
    }
    y[i] %= K * 2;
    if (y[i] >= K){
      y[i] -= K;
      x[i] += K;
    }
    x[i] %= K * 2;
  }
  vector<vector<int>> d(K * 2 + 1, vector<int>(K * 3 + 1, 0));
  for (int i = 0; i < N; i++){
    for (int dy = -1; dy < 3; dy++){
      for (int dx = -1; dx < 4; dx++){
        if ((dy + dx) % 2 == 0){
          int y2 = y[i] + dy * K;
          int x2 = x[i] + dx * K;
          d[clamp(y2, 0, K * 2)][clamp(x2, 0, K * 3)]++;
          d[clamp(y2 + K, 0, K * 2)][clamp(x2, 0, K * 3)]--;
          d[clamp(y2, 0, K * 2)][clamp(x2 + K, 0, K * 3)]--;
          d[clamp(y2 + K, 0, K * 2)][clamp(x2 + K, 0, K * 3)]++;
        }
      }
    }
  }
  for (int i = 0; i <= K * 2; i++){
    for (int j = 1; j <= K * 3; j++){
      d[i][j] += d[i][j - 1];
    }
  }
  for (int i = 0; i <= K * 3; i++){
    for (int j = 1; j <= K * 2; j++){
      d[j][i] += d[j - 1][i];
    }
  }
  int ans = 0;
  for (int i = 0; i < K * 2; i++){
    for (int j = 0; j < K * 3; j++){
      ans = max(ans, d[i][j]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 27692