akhauriyash/Code-Regression huggingface dataset:
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

int i_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int i_asort(const void* a, const void* b) {
	return(*(int*)a - *(int*)b);
}


int i_gcd(int a, int b);
int i_gcd(int a, int b) {
	if (!b)return a;
	return i_gcd(b, a % b);
}
int i_lcm(int a, int b);
int i_lcm(int a, int b) {
	return (a * b) / i_gcd(a, b);
}
int ll_gcd(ll a, ll b);
int ll_gcd(ll a, ll b) {
	if (!b)return a;
	return ll_gcd(b, a % b);
}
int ll_lcm(ll a, ll b);
int ll_lcm(ll a, ll b) {
	return (a * b) / ll_gcd(a, b);
}

// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
//ll _pfact(ll a);
//static ll pf[100000000];
//static ll pc;
//
//ll _pfact(ll a) {
//	long i, r;
//	if (a % 2 == 0) {
//		pf[pc] = 2; pc++;
//		return(_pfact(a / 2));
//	}
//	r = sqrt(a);
//	for (i = 3; i <= r; i += 2) {
//		if (a % i == 0) {
//			pf[pc] = i; pc++;
//			return(_pfact(a / i));
//		}
//	}
//	if (a != 1) {
//		pf[pc] = a; pc++;
//	}
//	return 0;
//
//}

//同じものの最初の文字をNULLにして降順
int _sort(const void* a, const void* b);
int _sort(const void* a, const void* b) {
	char rc;

	rc = strcmp((char*)b, (char*)a);
	if (rc == 0) {
		*(char*)a = 0x00;
		return(1);
	}
	return(rc);
}

#pragma endregion



//ABC 085 C - Otoshidama
int main(void) {
	int i,j,k,ii,jj,kk,n;
	ll  y;
 
	scanf("%d %lld",&n,&y);
	y /= 1000;
	ii = y / 10;
	jj = (!ii) ? y / 5 : n;

	ll tmp = 0;
	for (i = ii; i >= 0; i--) {
		for (j = n-i; j >= 0; j--) {
			tmp = (ll)i * 10 + (ll)j * 5 + (ll)n-i-j;
			if (tmp == y) {
				printf("%d %d %d\n", i,j,n-i-j);
				return 0;
			}
		}
	}
	printf("-1 -1 -1\n");

	return 0;
}




Measured memory_bytes: 1704
Bingo=[0]*9
correct=[]
A=list(map(int,input().split()))
for i in range(3):
    correct.append(A[i])
A=list(map(int,input().split()))
for i in range(3):
    correct.append(A[i])
A=list(map(int,input().split()))
for i in range(3):
    correct.append(A[i])
N=int(input())
for i in range(N):
    a=int(input())
    for j in range(9):
        if a==correct[j]:
            Bingo[j]=1
            break
if Bingo[0]==Bingo[1]==Bingo[2]==1:
    print("Yes")
elif Bingo[3]==Bingo[4]==Bingo[5]==1:
    print("Yes")
elif Bingo[6]==Bingo[7]==Bingo[8]==1:
    print("Yes")
elif Bingo[0]==Bingo[3]==Bingo[6]==1:
    print("Yes")
elif Bingo[1]==Bingo[4]==Bingo[7]==1:
    print("Yes")
elif Bingo[2]==Bingo[5]==Bingo[8]==1:
    print("Yes")
elif Bingo[0]==Bingo[4]==Bingo[8]==1:
    print("Yes")
elif Bingo[2]==Bingo[4]==Bingo[6]==1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
n = int(input())
a = input().split()
for i in range(n):
    a[i] = int(a[i])
ans = 1
flg = False

for i in range(n):
    if a[i] == 0:
        ans = 0
        break
if ans == 0 :
    print(ans)
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            flg = True
            break
    if flg:
        print(-1)
    else:
        print(ans)

Measured memory_bytes: 19404
import itertools
from collections import Counter

n = int(input())
al = list(map(int, input().split()))

arr = [0]
arr += list(itertools.accumulate(al))
c = Counter(arr)
ans = 0

for v in c.values():
    ans += v * (v - 1) // 2  # vC2

print(ans)


Measured memory_bytes: 44404
#include <bits/stdc++.h>
using namespace std;
#define endl "\n" 
#define ll long long
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set 
#define mod 1000000007
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define int long long
int dp[101][100005];

int helper(int *wt, int *val, int n, int index, int w) {
    if(w == 0) {
        return 0;
    }
    if(index == n-1) {
        if(wt[index] <= w) {
            return val[index];
        } else {
            return 0;
        }
    }
    if(dp[index][w] != -1) return dp[index][w];
    int ans = imin;
    if(wt[index] <= w) {
        ans = val[index] + helper(wt, val, n, index+1, w-wt[index]);
    }
    ans = max(ans, helper(wt, val, n, index+1, w));
    return dp[index][w] = ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof(dp));
    int n, w; cin >> n >> w;
    int val[n], wt[n];
    for(int i = 0; i < n; i++) {
        cin >> wt[i] >> val[i];
    }
    cout << helper(wt, val, n, 0, w);
    return 0;
}

Measured memory_bytes: 82516
def smaller(x, y):
	if x < y:
		return x
	return y

H, W = map(int, input().split())
C = []
for i in range(0, 10):
	C.append(list(map(int, input().split())))
A = []
for i in range(0, H):
	A.append(list(map(int, input().split())))
magic = []
for i in range(0, 10):
	magic.append(C[i][1])
for i in range(0, 10):
	notvisited = []
	for j in range(0, 10):
		notvisited.append(True)
	notvisited[i] = False
	queue = [[i, notvisited, 0]]
	while queue != []:
		now = queue.pop(0)
		if now[2] < magic[i]:
			if now[0] == 1:
				magic[i] = now[2]
			else:
				for j in range(0, 10):
					if now[1][j] and now[2]+C[now[0]][j] < magic[i]:
						newnotvisit = []
						for k in range(0, 10):
							if j == k:
								newnotvisit.append(False)
							else:
								newnotvisit.append(now[1][k])
						queue.append([j, newnotvisit, now[2]+C[now[0]][j]])
sum = 0
for i in range(0, H):
	for j in range(0, W):
		if A[i][j] != -1:
			sum += magic[A[i][j]]
print(sum)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned char ubyte;

const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int INF = (int)1e9 + 5;
const ll LINF = (ll)1e18 + 5;

bool eq(double a, double b) {
	return fabs(a - b) < EPS;
}

template<class T>
T sqr(const T & x) { return x * x; }

template<class T> 
ll abs(const T & x) { return x < 0 ? -x : x; }

template<class T>
ll myround(const T & x) { return x < 0 ? x - 0.5 : x + 0.5; }

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

template<class T>
ostream & operator <<(ostream & os, const vector<T> & v) {
	os << "{";
	for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) {
		os << *it;
		if ((it + 1) != v.end()) os << ", ";
	}
	os << "}";
	return os;
}

template<class P, class Q>
ostream & operator <<(ostream & os, const pair<P, Q> & p) {
	return os << "(" << p.first << ", " << p.second << ")";
}

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

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

bool opposite(char a, char b) {
	if (a > b) swap(a, b);
	if (a == 'N' && b == 'S') return true;
	if (a == 'E' && b == 'W') return true;
	return false;
}

int main() {
	//srand(time(0));
#ifdef LOCAL 
	freopen("input.txt", "r", stdin);
#else
#endif

	string s;
	
	cin >> s;

	auto z = set<char>(all(s));

	if (z.size() == 4) cout << "Yes";
	else if (z.size() == 2 && opposite(*z.begin(), *(++z.begin()))) cout << "Yes";
	else cout << "No";

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pa) {
  return os << "(" << pa.first << ", " << pa.second << ")";
}

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }


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

  long long cur = 0;
  rep(i, 1000010) {
    cur = (cur * 10) % k;
    cur = (cur + 7) % k;
    if (cur == 0) {
      print(i+1);
      return 0;
    }
  }
  print(-1);

  return 0;
}

Measured memory_bytes: 3648
n,m,c=map(int,input().split())
b_lists=list(map(int,input().split()))
true_num=0
for i in range (1,n+1):
  judge=0
  a_lists=list(map(int,input().split()))
  for j in range (1,m+1):
    judge=judge+b_lists[j-1]*a_lists[j-1]
  if judge+c>0:
    true_num=true_num+1
  else:
    true_num=true_num
print(true_num)

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] A = new int[N];
        int[] B = new int[N];
        int[] C = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = sc.nextInt();
        Arrays.sort(A);

        for (int i = 0; i < N; i++)
            B[i] = sc.nextInt();
        Arrays.sort(B);

        for (int i = 0; i < N; i++)
            C[i] = sc.nextInt();
        Arrays.sort(C);

        long[] up = new long[N];
        long[] dn = new long[N];

        int j = N - 1;
        for (int i = N - 1; i >= 0; i--) {
            for (; j >= 0; j--) {
                if (A[j] < B[i]) {
                    up[i] = (long)(j + 1); // record how many a is less at B[i];
                    break;
                }
            }

            if (j < 0) break;
        }

        j = 0;
        for (int i = 0; i < N; i++) {
            for (; j < N; j++) {
                if (C[j] > B[i]) {
                    dn[i] = (long) N - j;
                    break;
                }
            }

            if (j > N) break;
        }

        long res = 0;

        for (int i = 0; i < N; i++) {
                res += up[i] * dn[i];
        }

        System.out.println(res);
    }




}


Measured memory_bytes: 95888
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        long N = Reader.Long() + 1;
        var ans = new List<int>();
        int i = Enu.Range(0, 60).Last(x => (N >> x & 1) == 1) - 1;
        ans.Add(1);

        for (int num = 2; i >= 0; i--)
        {
            if ((N >> i & 1) == 1) ans.Insert(0, num++);
            if (i != 0) ans.Add(num++);
        }
        ans.AddRange(Enu.Range(1, ans.Count));

        Console.WriteLine(ans.Count + "\n" + string.Join(" ", ans));
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { Dispose(); A = new string[0]; }
    public static void Set(TextReader r) { Init(); reader = r; }
    public static void Set(string file) { Init(); reader = new StreamReader(file); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    public static void Dispose() { reader.Dispose(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

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

const int maxn=2e6+7;
struct node{
    int sx,ey;
}a[maxn];

int main (){
    string ss;cin>>ss;
    int sz=ss.size();
    stack<char>sta;
    for(int i=0;i<sz;i++){
        if(sta.empty()) sta.push(ss[i]);
        else if(ss[i]=='C'&&sta.top()=='B') sta.pop(),sta.push('D');
        else sta.push(ss[i]);
    }
    ss.clear();
    while(!sta.empty()) ss+=sta.top(),sta.pop();
    //cout<<ss<<endl;
    ll ans=0;
    reverse(ss.begin(),ss.end());
    sz=ss.size();
    //for(int i=0;i<=sz;i++) a[i].sx=a[i].ey=i;
    int kk=0;
    for(int i=0;i<sz;i++){
        if(ss[i]=='D') {
            int cnt=0;
            for(int j=i-1;j>=0;j--) {
                if(ss[j]=='A') cnt++;
                else break;
            }
            kk+=cnt;
            ans+=kk;
        }
        else if(ss[i]!='A') kk=0;
    }
    //for(int i=0;i<sz;i++) cout<<i<<" "<<a[i].sx<<" "<<a[i].ey<<endl;
    cout<<ans<<endl;
    return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001


int main(){
  cin.sync_with_stdio(false);
  int n;
  while(cin >> n, n) {
    vector<P> juery(n);
    rep(i, n) cin >> juery[i].fi >> juery[i].se;
    int m;
    cin >> m;
    vector<P> move;
    int x = 10, y = 10;
    rep(i, m) {
      char d;
      int l;
      cin >> d >> l;
      switch(d) {
        case 'N':
        rep(j, l) move.pb(P(x, ++y)); break;
        case 'E':
        rep(j, l) move.pb(P(++x, y)); break;
        case 'S':
        rep(j, l) move.pb(P(x, --y)); break;
        case 'W':
        rep(j, l) move.pb(P(--x, y)); break;
      }
    }

    bool ok;
    rep(i, n) {
      ok = false;
      rep(j, move.size()) {
        if (juery[i] == move[j]) ok = true;
      }
      if (!ok) break;
    }

    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3116
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        long h = Long.parseLong(sc.next());
        
        long ans = 0;
        long x = 1;
        while(h > 0){
            ans += x;
            x *= 2;
            h /= 2;
        }
        
        System.out.println(ans);
    }
}

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

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

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

int main() {
    int X, Y;
    cin >> X >> Y;
    if (Y%2) {
        cout << "No" << endl;
        return 0;
    }
           
    int AK = X*4;
    int AT = X*2;

    if( Y >= AT && Y <= AK) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;


    return 0;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

constexpr ll MOD = 1'000'000'007;
int H, W, K;
ll dp1[8], dp2[110][10];

ll rec(int r, int c){
    if(r == H){
        return c == K;
    }

    if(dp2[r][c] != -1){
        return dp2[r][c];
    }

    ll cnt = 0;

    if(c == 0 || c == W - 1){
        cnt = dp1[std::max(W-2, 0)] * rec(r + 1, c) % MOD;
    }else{
        cnt = dp1[std::max(c-1, 0)] * dp1[std::max(W-c-2, 0)] % MOD * rec(r + 1, c) % MOD;
    }

    if(c + 1 < W){
        cnt = (cnt + dp1[std::max(c-1, 0)] * dp1[std::max(W-c-3, 0)] % MOD * rec(r + 1, c + 1) % MOD) % MOD;
    }

    if(c - 1 >= 0){
        cnt = (cnt + dp1[std::max(c-2, 0)] * dp1[std::max(W-c-2, 0)] % MOD * rec(r + 1, c - 1) % MOD) % MOD;
    }

    return dp2[r][c] = cnt;
}

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

    dp1[0] = 1;
    for(int i=1;i<=7;++i){
        dp1[i] = (dp1[i-1] + dp1[std::max(i-2, 0)]) % MOD;
    }

    std::cin >> H >> W >> K;

    K -= 1;

    memset(dp2, -1, sizeof(dp2));

    int cnt = rec(0, 0);
    std::cout << cnt << std::endl;
}


Measured memory_bytes: 256
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key = lambda x: (x[1], x[0]))

def main():
    current = 0
    for i in range(N):
        current += X[i][0]
        if current > X[i][1]:
            print('No')
            return
    print('Yes')
    return

main()

Measured memory_bytes: 67828
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

ll dp[105][100005];

int main(){
  int N, W;
  cin >> N >> W;
  vector<ll> w(N), v(N);
  rep(i, N) cin >> w[i] >> v[i];

  dp[0][0] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j <= W; j++){
      if(w[i] <= j)dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
      else dp[i + 1][j] = dp[i][j];
    }
  }
  cout << dp[N][W] << endl;
  return 0;
}


Measured memory_bytes: 79360
fun main(args: Array<String>) {
    val N = nextInt()
    val e = IntArray(N + 1)
    for (i in 2 .. N) {
        var cur = i
        for (j in 2 .. i) {
            while (cur % j == 0) {
                e[j] += 1
                cur /= j
            }
        }
    }
    fun num(m: Int) = e.reduce { acc, x -> acc + (if (x >= m - 1) 1 else 0) }
    val n75 = num(75)
    val n25 = num(25)
    val n15 = num(15)
    val n5 = num(5)
    val n3 = num(3)
    val r5x5x3 = (n5 * (n5 - 1) * (n3 - 2)) / 2
    val r15x5 = n15 * (n5 - 1)
    val r25x3 = n25 * (n3 - 1)
    val r75 = n75
    println(r75 + r25x3 + r15x5 + r5x5x3)
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())


Measured memory_bytes: 33696
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x


def main():
    import sys

    readline = sys.stdin.buffer.readline

    N, Q = map(int, readline().split())
    tree = UnionFind(N)
    res = []
    for _ in range(Q):
        t, u, v = map(int, readline().split())
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 18904
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vi2;
typedef vector<vi2> vi3;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<vll> vll2;
typedef vector<vll2> vll3;
typedef vector<bool> vb;

#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define umap unordered_map
#define uset unordered_set
#define vec vector
#define loop(a) for (auto &x : a)
#define all(a) a.begin(), a.end()
#define mp make_pair

int n;
vi a, b;
vll2 cache;

ll dfs(int left, int right) {
    if (left > right) {
        return 0;
    }
    if (cache[left][right] != -1) {
        return cache[left][right];
    }
    int which = n - (right - left + 1);
    ll ans1 = dfs(left + 1, right) + abs(left - b[which]) * a[b[which]];
    ll ans2 = dfs(left, right - 1) + abs(right - b[which]) * a[b[which]];
    return cache[left][right] = max(ans1, ans2);
}

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

    cin >> n;
    a = vi(n);
    loop(a) {
        cin >> x;
    }
    b = vi(n);
    rep(i, 0, n) {
        b[i] = i;
    }
    sort(all(b), [&](int x, int y) {
        return a[x] > a[y];
    });
    cache = vll2(n, vll(n, -1));
    cout << dfs(0, n - 1) << el;
}


Measured memory_bytes: 34548
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int manhattan(int x1,int y1,int x2,int y2);

int main()
{
	int n,i,m,tsa,flag=1;
	int t[100010][3]={0};
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d %d",&(t[i][0]),&(t[i][1]),&(t[i][2]));
		m=manhattan(t[i-1][1],t[i-1][2],t[i][1],t[i][2]);
		tsa=t[i][0]-t[i-1][0];
		if(tsa<m||(tsa-m)%2==1)flag=0;
	}
	if(flag)printf("Yes");
	else printf("No");
}

int manhattan(int x1,int y1,int x2,int y2)
{
	return (abs(x1-x2)+abs(y1-y2));
}

Measured memory_bytes: 1280
N = int(input())
start = 0
end = 1
Judge = [(1, 1)]
for i in range(1, abs(N)):
    start_ = start + (-2) ** i
    end_ = end + (-2) ** i
    Judge.append((start_, end_))
    start = min(start, start_)
    end = max(end, end_)
    if start <= N <= end:
        break

n = len(Judge)
A = ['0'] * n

for i in range(n)[::-1]:
    start, end = Judge[i]
    if start <= N <= end:
        A[i] = '1'
        N -= (-2) ** i
print(''.join(A[::-1]))


Measured memory_bytes: 61992
#include <iostream>
using namespace std;
int main()
{
    int D;
    cin >> D;
    if(D==25) cout << "Christmas" << endl;
    else if(D==24) cout << "Christmas Eve" << endl;
    else if(D==23) cout << "Christmas Eve Eve" << endl;
    else cout << "Christmas Eve Eve Eve" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    INCANT;
    int n, a;
    bool flag = false;
    cin>>n;
    rep(i, n) {
        cin>>a;
        if(a % 2) flag = true;
    }
    if(flag) cout<<"first"<<endl;
    else cout<<"second"<<endl;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split().map(&:to_i)

sum = a[0].abs + a[n-1].abs
(n-1).times do |i|
  sum += (a[i+1] - a[i]).abs
end

puts sum - (a[0].abs + (a[1] - a[0]).abs) + a[1].abs

(n-2).times do |i|
  puts sum - ((a[i+1] - a[i]).abs + (a[i+2] - a[i+1]).abs) + (a[i+2] - a[i]).abs
end

puts sum - ((a[n-1] - a[n-2]).abs + a[n-1].abs) + a[n-2].abs


Measured memory_bytes: 12172
#include <iostream>

using namespace std;

int main() {
    uint16_t H, W;

    while (cin >> H >> W) {
        if (H == 0 && W == 0)
            break;

        for (uint16_t i = 0; i < H; i++) {
            for (uint16_t j = 0; j < W; j++)
                if (i == 0 || i == H-1 || j == 0 || j == W-1)
                    cout << "#";
                else
                    cout << ".";

            cout << endl;
        }

        cout << endl;
    }

    return 0;
}

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

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N;
    scan(N);
    auto H = readln.split.to!(int[]);
    auto ans = new int[](N);
    foreach (i ; 1 .. N) {
        if (H[i - 1] >= H[i]) ans[i] = ans[i - 1] + 1;
        else ans[i] = 0;
    }
    writeln(ans.reduce!max);
}







void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define AC cout << "AC" << endl;
#define WA cout << "WA" << endl;

#define out(s) cout << s << endl;

#define ll long long
#define ull unsigned long long

const unsigned int BIT_FLAG_0 = (1 << 0);  // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1);  // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2);  // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3);  // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4);  // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5);  // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6);  // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7);  // 0000 0000 1000 0000

const double PI = 3.14159265358979323846;

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

#define H_MAX 500
#define W_MAX 500
#define INF 1e9 + 7

int main() {
    int N, cnt = 0, cnt2 = 0;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int x = i;
        cnt = 0;
        while (x) {
            cnt++;
            x /= 10;
        }
        if (cnt % 2 == 1) {
            cnt2++;
        }
    }
    cout << cnt2 << endl;
}


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

int main() {
	string S;
    cin >> S;
    int up = (S[0] - '0') * 10 + S[1] - '0';
    int down = (S[2] - '0') * 10 + S[3] - '0';
    if (1 <= up && up <= 12) {
        if (1 <= down && down <= 12) {
            cout << "AMBIGUOUS" << endl;
        } else {
            cout << "MMYY" << endl;
        }
    } else if (1 <= down && down <= 12) {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll L, R;
    cin >> L >> R;
    ll ans = INF;
    if (R - L <= 2019) {
        rep2(i, L, R) {
            rep2(j, i + 1, R + 1) {
                ans = min(ans, (i * j) % 2019);
            }
        }
    } else {
        ans = 0;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main() {
  int W, H, x, y;
  scanf("%d %d %d %d", &W, &H, &x, &y);

  printf("%.16f", 0.5*H*W);

  char s[100000];
  memset(s, '0', sizeof s);
  fwrite(s, 1, sizeof s, stdout);

  putchar(' ');
  puts((x+x == W && y+y == H)? "1": "0");
}


Measured memory_bytes: 384
#include<stdio.h>

int main(){
int i,j,yama[10],temp;
for(i=0;i<10;i++){
scanf("%d",&yama[i]);
}
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(yama[i]>yama[j]){
temp=yama[i];
yama[i]=yama[j];
yama[j]=temp;
}
}
}
for(i=0;i<3;i++){
printf("%d\n",yama[i]);
}
return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<pair<ll,ll> > > vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) x.begin() , x.end()
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define F first
#define S second
#define left (node << 1)
#define right (node << 1) + 1
#define pii pair<int,int> 
#define mii map<int,int>
#define vi vector<int>
#define umii unordered_map<int,int>
#define mod1 998244353
#define mod2 1000000007
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<": " <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define FILL(name,val) memset(name , val , sizeof(name))
#define repo(i,o,e) for(int i = o ; i < e ; i++)
#define rep(n) for(int i = 0 ; i < n ; i++)
const ll sz = 2e5+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve(){
    //
    int n;
    cin >> n;
    vector<int> dp(n+10 , 0) , v(n);
    rep(n){
        cin >> v[i];
    }
    dp[1] = abs(v[1] - v[0]);
    repo(i,2,n){
        dp[i] = min(abs(v[i-1] - v[i]) + dp[i-1] , dp[i-2] + abs(v[i-2] - v[i]));
    }
    cout << dp[n-1] << endl;
    //
    return;
}



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

Measured memory_bytes: 1024
a, b, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [0] * m
y = [0] * m
c = [0] * m
minval = int(1e10)
for i in range(m):
    x[i], y[i], c[i] = map(int, input().split())
    val = a[x[i]-1] + b[y[i]-1] - c[i]
    if minval > val:
        minval = val
print(min(min(a) + min(b), minval))

Measured memory_bytes: 23396
from collections import deque
n=int(input())
a=deque(sorted([int(input()) for _ in range(n)]))
b=deque([a.pop()])
i=0
while a:
  if max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[-1]-b[-1]):
    b.append(a.pop())
  elif max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[-1]-b[0]):
    b.appendleft(a.pop())
  elif max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[0]-b[0]):
    b.appendleft(a.popleft())
  else:
    b.append(a.popleft())
ans=0
for i in range(n-1):
  ans+=abs(b[i]-b[i+1])
print(ans)

Measured memory_bytes: 86260
#include<iostream>
#include<algorithm>
#include <vector>
#include <set>
using namespace std;
int main(){
	int a[2];
	cin>>a[0]>>a[1];
	int data[2];
	for(int i=0;i<2;i++){
		if(a[i]==2)data[i]=3;
		else if(a[i]==4)data[i]=2;
		else if(a[i]==6)data[i]=2;
		else if(a[i]==9)data[i]=2;
		else if(a[i]==11)data[i]=2;
		else data[i]=1;
	}
	
	if(data[0]==data[1])cout<<"Yes";
	else cout<<"No";
}


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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

long double PI = acos(-1.0);

long double solve(long double a, long double b, long double x) {
    auto tmp = a * a * b / 2;
    /*
    cout << "a; " << a << endl;
    cout <<" b:  " << b << endl;
    cout << "x: " << x << endl;
    cout << "tmp: " << tmp << endl;
    */
    if (tmp == x)
        return atan(b / a);
    if (x < tmp) {
        auto d = 2 * x / (a * b);
        // cout << "d1: " << d << endl;
        return atan(b / d);
    }
    // tmp > x
    auto d = 2 * (a * a * b - x) / (a * a);
    // cout << "d2: " << d << endl;
    return atan(d/a);
}

int main() {
    ios::sync_with_stdio(0);
    long double a, b, x;
    cout << fixed << setprecision(10);
    cin >> a >> b >> x;
    long double ans = solve(a, b, x);
    ans = ans / PI * 180;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))

int main(){
    int X, Y;
    cin >> X >> Y;
    cout << X + Y / 2 << endl;
}


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


int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    vector<int> T(N, 0);
    for (int i = 1; i < N; i++) {
        T[i] += T[i - 1];
        if (S[i - 1] == 'A' && S[i] == 'C') T[i]++;
    }

    int l, r;
    rep(_, Q) {
        cin >> l >> r;
        cout << T[r - 1] - T[l - 1] << "\n";
    }

    return 0;
}

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

int n, p[500005], z[500005];
vector<int> q[1 << 20];
const long long MOD = 1e9 + 7;
int main() {
    // freopen("data.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", p + i);
        p[i] ^= p[i - 1];
        q[p[i]].push_back(i);
        if (p[i] == 0)
            z[i] = z[i - 1] + 1;
        else
            z[i] = z[i - 1];
    }
    long long ans = 0;
    for (int x = 1; x < (1 << 20); ++x) {
        if (q[x].empty()) continue;
        if (p[n] == x || p[n] == 0) {
            int m = static_cast<int>(q[x].size());
            long long s1 = 0, s2 = 0, dp = 0;
            for (int i = 0; i < m; ++i) {
                dp = 1 + z[q[x][i]] * s1 - s2;
                dp %= MOD;
                if (dp < 0) dp += MOD;

                s1 += dp;
                s2 += dp * z[q[x][i]] % MOD;

                s1 %= MOD;
                s2 %= MOD;

                if (p[n] == 0) {
                    ans += dp;
                    ans %= MOD;
                }
            }
            if (p[n] == x) {
                ans += dp;
                ans %= MOD;
            }
        }
    }
    // Now deal with x=0 case.
    if (p[n] == 0) {
        long long s = 1;
        for (int i = 1; i < n; ++i) {
            if (p[i] == 0) {
                s = s * 2 % MOD;
            }
        }
        ans += s;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 38388
//解説あり
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int t[5005][5005];

int main(void) {
  string s;
  int n;
  cin >> n >> s;
  
  for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) {
    if (s[i]==s[j]) t[i][j] = 1;
  }
  
  int ans = 0;
  for(int i=1; i<n; i++) {
    int y = 0, x = i;
    while (y<n && x<n) {
      if (t[y][x]) {
        int c = 0, p = x;
        while (y<n && x<n && t[y][x] && y<p) {c++; x++;y++;}
        ans = max(ans, c);
      
      }
      x++; y++;
    }
  }
    

    cout << ans << endl;

	return 0;
}


Measured memory_bytes: 96768
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}


int main() {
  string s;
  cin >> s;
  int c0 = count(all(s),'0');
  int c1 = count(all(s),'1');
  cout << 2*min(c0,c1) << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <list>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

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

    // dp[i][j] : [i, j]が残ってる時の　次の手番 - そうじゃない方　の値
    vector<vector<ll>> dp(N, vector<ll>(N));
    for(int i=N-1; i>=0; --i)
        for(int j=i; j<N; ++j) {
            if(i == j)
                dp[i][j] = a[i];
            else
                dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]);
        }

    cout << dp[0][N-1] << endl;
    return 0;
}

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

int main(){
    string x;
    cin >> x;
    if((x[0] == x[1] && x[1] == x[2]) || (x[1] == x[2] && x[2] == x[3]))
        cout << "Yes" << endl;
        else
            cout << "No" << endl;
        return 0;
}

Measured memory_bytes: 256
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#define MAXN 100010
using namespace std;
struct Node
{
	int val,num;
};
bool operator<(Node a ,Node b)
{
	return a.val<b.val;
}
vector<Node>a[MAXN];
int pr[MAXN];
inline void pr_num(int x)
{
	for(int i=1;i<=6;i++)
	{
		pr[i]=x%10;
		x=x/10;
	}
	for(int i=6;i>=1;i--)
		putchar('0'+pr[i]);
}
struct City{
	int x,y;
}SA[MAXN];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		Node p;
		SA[i].x=x;
		p.num=i,p.val=y;
		a[x].push_back(p);
	}
	for(int i=1;i<=n;i++)
	{
		sort(a[i].begin(),a[i].end());
		for(int j=0;j<a[i].size();j++)
			SA[a[i][j].num].y=j+1;
	}
	for(int i=1;i<=m;i++)
	{
		pr_num(SA[i].x);
		pr_num(SA[i].y);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 7808
#include "bits/stdc++.h"
using namespace std;

#define rep(i, n)  for (int i = 0; i < (int) (n); i++)
#define Rrep(i, n) for (int i = ((int) n - 1); i >= 0; i--)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
#define INF 2e15
#define MOD 10e9 + 7

typedef vector <int> vint;
typedef long long    ll;



int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int n;
    int cnt = 0;
    cin >> n;
    vint seq(n, 0);
    vint min(n, -1);

    rep(i, n) {
        cin >> seq.at(i);
        if (i == 0) {
            min.at(i) = seq.at(i);
        }
        else {
            if (min.at(i - 1) > seq.at(i)) {
                min.at(i) = seq.at(i);
            }
            else {
                min.at(i) = min.at(i - 1);
            }
        }
    }


    rep(i, n) {
        if (seq.at(i) <= min.at(i)) {
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define sz(a) (int)((a).size())
#define fuck() cout<<"--------"<<endl
#define see(x) cout<<#x<<" = "<<x<<endl
#define see2(x,y) cout<<#x<<" = "<<x<<"::"<<#y<<" = "<<y<<endl 
const int mod=1000000007;
typedef pair<int,int> pii;
const int N=1e5+5;
bool check(string &s){
    int l=0,r=sz(s)-1;
    while(l<r){
        if(s[l++]!=s[r--]){
            return false;
        }
    }
    return true;
}
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    string s;
    cin>>s;
    int n=sz(s);
    string t1=s.substr(0,(n-1)/2);
    string t2=s.substr((n+3)/2-1);
    if(check(t1) and check(t2) and check(s)){
        cout<<"Yes";
    }
    else cout<<"No";
}

Measured memory_bytes: 256