akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int n, *x, *y;

double minkowski_inf() {
	double D = 0;
	for (int i = 0; i < n; i++)
		D = max(abs(x[i] - y[i]), D);
	return D;
}

double minkowski(int p) {
	double D = 0;
	for (int i = 0; i < n; i++)
		D += pow(abs(x[i] - y[i]), p);
	D = pow(D, 1.0 / p);
	return D;
}

int main() {
	cin >> n;
	x = new int[n];
	y = new int[n];
	for (int i = 0; i < n; i++)
		cin >> x[i];
	for (int i = 0; i < n; i++)
		cin >> y[i];
	printf("%.8f\n", minkowski(1));
	printf("%.8f\n", minkowski(2));
	printf("%.8f\n", minkowski(3));
	printf("%.8f\n", minkowski_inf());
	delete[] x;
	delete[] y;
	return 0;
}

Measured memory_bytes: 1272
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[100000],i,flag,j;
    cin>>a[0];
    for(i=1; ;i++)
    {
        flag=0;
        if(a[i-1]%2==0)
            a[i]=a[i-1]/2;
        else a[i]=(3*a[i-1])+1;
        for(j=i-1;j>=0;j--)
        {
            if(a[i]==a[j]) flag=1;
        }
        if(flag==1) break;
    }
    cout<<i+1<<endl;
    return 0;

}


Measured memory_bytes: 256
main = do
    [n, y] <- map read . words <$> getLine
    let ans = [[a, b, c] | a <- [0 .. n], b <- [0 .. (n - a)], let c = n - a - b, 10000 * a + 5000 * b + 1000 * c == y]
    putStrLn $ unwords $ map show $ if null ans then [-1, -1, -1] else head ans

Measured memory_bytes: 1020
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  string s,t;
  cin >>s;
  cin >>t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if(s<t){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,i,sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
            //cout<<i<<" ";
            sum+=i;
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3624
T = list(map(int, list(input())))

def search(ops, p):
    if p < 3:
        ops[p] = 1
        ret_ops = search(ops, p+1)
        if T[p+1] == 0 or sum(T[0:1] + [t * op for (t, op) in zip(T[1:], ret_ops)]) == 7:
            return ret_ops
        else:
            ops[p] = -1
            return search(ops, p+1)
    else:
        return ops

ops = search([None, None, None], 0)

T = list(map(str, T))
ops = ["+" if op == 1 else "-" for op in ops]
print("{}{}=7".format(T[0], "".join(map(lambda x: "".join(x), zip(ops, T[1:])))))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    vector<ll> b(N + 1, 0);
    for (int i = 1; i < N + 1; i++) {
        b[i] = b[i - 1] + (a[i - 1] > 0 ? a[i - 1] : 0);
    }
    vector<ll> c(a.size() + 1, 0);
    partial_sum(a.begin(), a.end(), c.begin() + 1);

    ll ans = 0;
    for (int i = 0; i < N - K + 1; i++) {
        ll sum = (b[i] - b[0]) + (b[N] - b[i + K]);
        sum += max(0LL, c[i + K] - c[i]);
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

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

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int r = fs.nextInt();
		
		System.out.println(r*r);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

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

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

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

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

}


Measured memory_bytes: 32776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll h,w,a,b;
	cin>>h>>w>>a>>b;
	bool ch=true;
	for(ll i=0;i<h;i++){
		if(i==b){
			ch=false;
		}
		for(ll j=0;j<w;j++){
			if(j<a){
				cout << abs(ch-1);
			}
			else{
				cout << abs(1-abs(ch-1));
			}
		}
		cout <<endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 1280
////////////////////////
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
namespace my {
char itoc(int i) { return i + '0'; }
int ctoi(char c) { return c - '0'; }
ll gcd(ll a, ll b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
ll lcm(ll a, ll b) { return a * b / my::gcd(a, b); }
vector<pair<ll, ll>> primeFac(ll n) {
  vector<pair<ll, ll>> ret;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) continue;
    ll exp = 0;
    while (n % i == 0) {
      n /= i;
      exp++;
    }
    ret.push_back(make_pair(i, exp));
  }
  if (n != 1) ret.push_back(make_pair(n, 1));
  return ret;
}
}  // namespace my
////////////////////////

int main() {
  int n;
  cin >> n;
  if (n % 1000 == 0)
    cout << 0 << endl;
  else
    cout << 1000 - (n % 1000) << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rp(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll=long long;
using P=pair<int,int>;
using G=vector<vector<int>>;

int main(){
    vector<int> a(3);
    rp(i,3) cin >> a[i];
    sort(a.begin(),a.end());
    cout << a[0]*a[1]/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
 
#ifdef _WIN32
    #define gx getchar
    #define px putchar
    #define ps putchar(' ')
    #define pn putchar('\n')
    #define DEBUG 1
#else
    #define gx getchar_unlocked
    #define px putchar_unlocked
    #define ps putchar_unlocked(' ')
    #define pn putchar_unlocked('\n')
    #define DEBUG 0
#endif
 
#define rep(i,j,k) for(ll i=0;i<j;i+=k)
//input
void scan(int &n)
{
    int sign = 1;
    n = 0;
    char c = gx();
    while( c < '0' || c > '9' )
    {
        if( c == '-' ) sign = -1;
        c = gx();
    }
    while( c >= '0' && c <= '9' ) n = (n<<3) + (n<<1) + c - '0', c = gx();  n = n * sign;
}
void lscan(ll &n)
{
    int sign = 1;
    n = 0;
    char c = gx();
    while( c < '0' || c > '9' )
    {
        if( c == '-' )
        sign = -1;
        c = gx();
    }
    while( c >= '0' && c <= '9' ) n = (n<<3) + (n<<1) + c - '0', c = gx();  n = n * (ll)(sign);
}
int sscan(char a[])
{
    char c = gx();
    while(c==' ' || c=='\n') c=gx();
    int i=0;
    while(c!='\n')a[i++] = c,c=gx();
    a[i]=0;
    return i;
}
int wscan(char a[])
{
    char c = gx();
    while(c==' ' || c=='\n') c=gx();
    int i=0;
    while(c!='\n' && c!=' ')a[i++] = c,c=gx();
    a[i]=0;
    return i;
}
 
//output
void print(int n)
{
    if(n<0)
    {
        n=-n;
        px('-');
    }
    int i=10;
    char o[10];
    do{o[--i] = (n%10) + '0'; n/=10;}while(n);
    do{px(o[i]);}while(++i<10);
}
void lprint(ll n)
{
    if(n<0LL)
    {
        n=-n;
        px('-');
    }
    int i=21;
    char o[21];
    do{o[--i] = (n%10LL) + '0'; n/=10LL;}while(n);
    do{px(o[i]);}while(++i<21);
}
void sprint(const char a[])
{
    const char *p=a;
    while(*p)px(*p++);
}
 
 
ll po(ll a, ll b, ll m)
{
	ll x=1,y=a;
	while(b > 0)
	{
		if(b%2 == 1)
		{
			x=(x*y);
			if(x>m) x%=m;
		}
		y = (y*y);
		if(y>m) y%=m;
		b /= 2;
	}
	return x;
}
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int main()
{
	char c;
	cin>>c;
	if(c>=65&&c<=92)
		cout<<'A'<<endl;
	else
		cout<<'a'<<endl;
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

int main()
{
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n,y;
    int man=-1,go=-1,sen=-1;
    cin>> n >> y;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n-i; j++){
            int k = n-i-j;
            if(k<0) k=0;
            if(i*10000 + j*5000 + k*1000 == y){
                man = i;
                go = j;
                sen = k;
            }
        }
    }
    cout << man << " " << go << " "<< sen << endl;
}

Measured memory_bytes: 256
from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_left(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])

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

const int INF = 100000;

int d[200][200];
int n;

int warchall_floyd(){
	int res = 0;
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}
}

using Graph = vector<vector<int>>;

// 二部グラフ判定
vector<int> color;
bool dfs(const Graph &G, int v, int cur = 0) {
    color[v] = cur;
    for (auto next_v : G[v]) {
        // 隣接頂点がすでに色確定していた場合
        if (color[next_v] != -1) {
            if (color[next_v] == cur) return false; // 同じ色が隣接したらダメ
            continue;
        }

        // 隣接頂点の色を変えて、再帰的に探索 (一回でも false が返ってきたら false)
        if (!dfs(G, next_v , 1 - cur)) return false;
    }
    return true;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	Graph G(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			char c; cin >> c;
			d[i][j] = (c - '0');
			if(d[i][j]){
				G[i].push_back(j);
				G[j].push_back(i);
			}
			if(i != j && d[i][j] == 0) d[i][j] = INF;
		}
	}
	// 探索
    color.assign(n, -1);
    bool is_bipartite = true;
    for (int v = 0; v < n; ++v) {
        if (color[v] != -1) continue; // v が探索済みだったらスルー
        if (!dfs(G, v)) is_bipartite = false;
    }
    if(!is_bipartite){
    	cout << -1 << endl;
    	return 0;
    }
    warchall_floyd();
    int ans = 0;
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < n; j++){
    		if(d[i][j] != INF) ans = max(ans, d[i][j]);
    	}
    }
    ans++;
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 896
N=int(input());t=[0]*(N+1);x=[0]*(N+1);y=[0]*(N+1)
for i in range(N):t[i+1],x[i+1],y[i+1]=map(int,input().split())
flag=1
for i in range(N):
    dl = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i])
    dt = t[i + 1] - t[i]
    if dl > dt or (dl - dt) % 2 == 1:
        flag = 0
        break
if flag == 1:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 11636
n, m = map(int, input().split())
h = list(map(int, input().split()))

ma = [0]*n

for i in range(m):
    a = 0
    b = 0
    a, b = map(int, input().split())
    
    ma[a-1] = max(ma[a-1], h[b-1])
    ma[b-1] = max(ma[b-1], h[a-1])
    
ans = 0

for i in range(n):
    if h[i] > ma[i]:
        ans = ans+1

print(ans)

Measured memory_bytes: 20140
// ABC142B.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;
int main()
{
	int ans=0; // 答えを入れる変数を準備する　整数
	int N, K;
	cin >> N >> K; //人数と乗るための身長を読み込む
	int h; //仲間の身長を読み込む
	for (int i = 0; i < N; i++)
	{
		cin >> h;
		if (h>=K)
		{
			ans++;
		}
	}
	cout << ans << endl; // 答えを出力する
}


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

flag=0
ans=0

for i in range(0,N-1):
    if H[i+1]-H[i]<=0:
        flag+=1
    else:
        ans=max(ans,flag)
        flag=0
        
ans=max(ans,flag)
        
print(ans)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
ll dp[maxn];
ll a[maxn],b[maxn],f[maxn];
char s[maxn];
ll ksm(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>s+1;
	f[0]=1;
	for(int i=1;i<maxn;i++) f[i]=f[i-1]*i%mod;
	int n=strlen(s+1);
	for(int i=n;i>=1;i--) a[n-i+1]=s[i]-'0';
	ll ans=0;
	for(int i=n;i>=1;i--){
		b[i]=b[i+1]+(a[i]==1);
	}
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			ans+=ksm(2,b[i+1])*ksm(3,i-1)%mod;
			ans%=mod;
		}
	}
	ans=(ans+ksm(2,b[1]))%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2688
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    
        var sc = new Scanner(System.in);
    
        int n = Integer.parseInt(sc.next());
        var a = new long[n];
        for(int i = 0; i < n; i++){
            a[i] = Long.parseLong(sc.next());
            if(a[i] == 0){
                System.out.println(0);
                return;
            }
        }
        var b = BigInteger.valueOf(1);
        for(int i = 0; i < n; i++){
            b = b.multiply(BigInteger.valueOf(a[i]));
            if(b.compareTo(BigInteger.valueOf(1_000_000_000_000_000_000L)) > 0){
                b = BigInteger.valueOf(-1);
                break;
            }
        }
        System.out.println(b);
    }
}

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

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

    long long A[n + 1] = {};
    for(int i = 1; i <= n; i++){
        int tmp = i, j = 2;
        while(tmp > 1){
            if(tmp % j) j++;
            else{
                tmp /= j;
                A[j]++;
            }
        }
    }
    
    long long ans = 1;
    for(int i = 2; i <= n; i++){
        ans = (ans * (A[i] + 1)) % (int)(1e9 + 7);
    }
    cout << ans << endl; 

    return 0;
}

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

const int N = 8;

char masu[N][N];

bool check(int x, int y) {
    int m, n;

    for (m = 0; m < N; m++) {
        if (masu[m][y] == 'Q' && m != x) return false;
        if (masu[x][m] == 'Q' && m != y) return false;
    }

    m = x; n = y;
    while (m > 0 && n > 0)
        if (masu[--m][--n] == 'Q') return false;

    m = x; n = y;
    while (m < N-1 && n < N-1)
        if (masu[++m][++n] == 'Q') return false;

    m = x; n = y;
    while (m > 0 && n < N-1)
        if (masu[--m][++n] == 'Q') return false;

    m = x; n = y;
    while (m < N-1 && n > 0)
        if (masu[++m][--n] == 'Q') return false;

    return true;
}
bool dfs(int i) {
    if (i == N) return true;

    for (int j = 0; j < N; j++) {
        if (masu[i][j] == 'Q') {
            if (dfs(i+1)) return true;
        } else {
            if (check(i, j)) {
                masu[i][j] = 'Q';
                if (dfs(i+1)) return true;
                masu[i][j] = '.';
            }
        }
    }

    return false;
}

int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            masu[i][j] = '.';

    int k; cin >> k;
    for (int i = 0; i < k; i++) {
        int r, c; cin >> r >> c;
        masu[r][c] = 'Q';
    }

    dfs(0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << masu[i][j];
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int normalize(int x,int mod){
  x%=mod;
  if (x<0)x+=mod;
  return x;
}

struct GCD_POM{
  // d - to koncowe nwd, x i y to rozwiazania ax+by=nwd(a,b)
  int x,y,d;
};

int nww(int a,int b){
  return a/__gcd(a,b)*b;
}


GCD_POM EXT_GCD(int a,int b){
  if (b==0)return {1,0,a};
  GCD_POM syn=EXT_GCD(b,a%b);
  //b*x1+a%b*y1=g
  //b*x1+(a-(a/b)*b)*y1=g
  //b*x1+a*y1-b*(a/b)*y1
  //y1,(x1-(a/b)*y1)
  return {syn.y,syn.x-(a/b)*syn.y,syn.d};
}

int crt(vector<pii>c){
  // zwraca -1 kiedy nie ma rozwa, w przeciwnym wypadku wynik
  // wektor c postaci przystawanie, modulo w sensie x przystaje c[i].st mod c[i].nd 
  if (c.empty())return -1; // opcjonalnie w zaleznosci od zadania
  for (auto &it:c)normalize(it.st,it.nd);
  int ans=c.back().st,lcm=c.back().nd;
  c.pop_back();
  while (!c.empty()){
    pii now=c.back();
    c.pop_back();
    auto pom=EXT_GCD(lcm,now.nd);
    int x1=pom.x,d=pom.d;
    if ((now.st-ans)%d!=0)return -1;
    ans=normalize(ans+x1*(now.st-ans)/d%(now.nd/d)*lcm,lcm*now.nd/d);
    lcm=nww(lcm,now.nd);
  }
  return ans;
}
const int inf=1e18+9;
int ans=inf;
int32_t main(){
  BOOST;
  int n;
  cin>>n;
  if (n==2){
    cout<<"3";
    return 0;
  }
  else if (n==1){
    cout<<"1";
    return 0;
  }
  n*=2;
  for (int i=1;i*i<=n;i++){
    if (n%i==0){
      int n1=i,n2=n/i;
      //cout<<"KUZWA "<<n1<<" "<<n2<<" "<<(1100144%n1)<<" "<<(1100144%n2)<<"\n";
      int x=crt({{0,n1},{n2-1,n2}});
      if (x!=-1)ans=min(ans,x);
      n1=n/i,n2=i;
      x=crt({{0,n1},{n2-1,n2}});
      if (x>0)ans=min(ans,x);
      //cout<<"TERAZ "<<n1<<" "<<n2<<" "<<x<<"\n";
     
    }
  } 
  cout<<ans;
  return 0; 
}


Measured memory_bytes: 3676
#include<iostream>
#include<algorithm>
#include<utility>
#define MAXN 105
#define MAXW 10005
#define TOP 0
#define DIA 1
using namespace std;

int p[MAXN], c[MAXN][MAXW], g[MAXN][MAXW] = { 0 };
int N, W;

struct Items{
	int weight, value;
};

Items items[MAXN];

int price(){
	for (int i = 0; i <= N; i++){
		c[i][0] = 0;
	}
	for (int i = 1; i <= W; i++){
		c[0][i] = 0;
	}
	for (int n = 1; n <= N; n++){
		for (int w = 1; w <= W; w++){
			c[n][w] = c[n - 1][w];
			g[n][w] = TOP;
			if (w < items[n].weight) continue;
			else if (c[n][w] < c[n - 1][w - items[n].weight] + items[n].value)
			{
				c[n][w] = c[n - 1][w - items[n].weight] + items[n].value;
				g[n][w] = DIA;
			}
				
		}
	}
	return c[N][W];
}

int main(){
	cin >> N >> W;
	for (int i = 1; i <= N; i++){
		cin >> items[i].value >> items[i].weight;
	}
	cout << price() << endl;
	
}

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

int main(){
    int n;
    cin >> n;
    vector<int> array(n);
    for(int i=0;i<n;i++) cin >> array.at(i);
    vector<int> tairyoku(0);
    for(int i=1;i<=100;i++){
        int tai = 0;
        for(int j=0;j<n;j++){
            tai += (array.at(j) - i) * (array.at(j) -i);
        }
        tairyoku.push_back(tai);
    }
    int min = 10000000;
    for(int i=0;i<tairyoku.size();i++){
        if(min > tairyoku.at(i)) min = tairyoku.at(i);
    }
    cout << min << endl;
}

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

int main() {
    int l[210];
    int n;
    cin >> n;
    for (int i = 0; i < n * 2; i++) {
        cin >> l[i];
    }
    sort(l,l+2*n);
    int ans = 0;
    for (int i = 0; i < n * 2; i += 2) {
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int A, B, C, P, N, Ans;
  cin >> A >> B >> C;
  P = 0;
  Ans = 0;
  N = 1000000;
  
  for (int i = 0; i < N; i++) {
    Ans++;
    P += A;
    if (Ans % 7 == 0) {
      P += B;
    }
    if (P >= C) {
      break;
    }
  }
  
  cout << Ans << endl;
  
  return 0;
}


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

int main(){
  int N;
  cin>>N;
  int a[N];
  for (int i=0;i<N;i++){
    cin >>a[i];
  }
  sort(a,a+N);
  int count=0;
 
  for (int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      for(int k=j+1;k<N;k++){
        if(a[i]+a[j]>a[k]){
          count++;
        }
      }
    }
  }
  //cout<<N<<a[0]<<a[1]<<a[2]<<endl;
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
const int mod=1000000007;
long long power(long long a,int k){
    long long ans=1,y=a;
    while(k){
        if(k%2)
            ans=ans*y%mod;
        y=y*y%mod;
        k=k/2;
    }
    return ans;
}
long long fun[1<<17],ans=1;
int main(){
    long long n,m;
    scanf("%lld%lld",&n,&m);
    fun[0]=1;
    for(int i=1;i<1<<17;i++){
        fun[i]=fun[i-1]*i%mod;
    }
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            long long s=0;
            while (m%i==0) {
                m=m/i;
                s++;
            }
            ans=ans*fun[n+s-1]%mod*power(fun[n-1], mod-2)%mod*power(fun[s], mod-2)%mod;
        }
    }
    if(m>1)
        ans=ans*n%mod;
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1152
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
inner=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      inner+=1
outer=0
for i in range(n):
  for j in range(n):
    if a[i]>a[j]:
      outer+=1
ans=inner*k + outer*k*(k-1)//2
print(ans%mod)
#print(inner,' ',outer)

Measured memory_bytes: 3188
import java.util.Scanner;

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

        int x = sc.nextInt();
        int n = sc.nextInt();
        int[] p = new int[n];
        for(int i = 0; i<n; i++){
            p[i] = sc.nextInt();
        }

        int ans = -100000000;
        int ansLow, ansHigh;
        int count = 0;
        int matchNotAns = -1000000000;

        for(int j = 0; j<1000; j++){
            for(int k = 0; k<n; k++){
                if(x - j == p[k]){
                    count++;
                    matchNotAns = p[k];
                }
                else if(x + j == p[k]){
                    count++;
                    matchNotAns = p[k];
                }
            }
            if(count == 1 && j!=0){
                if(matchNotAns == x - j){
                    ans = x + j;
                }
                else if(matchNotAns == x + j){
                    ans = x - j;
                }
                break;
            }
            else if(count == 0){
                ans = x - j;
                break;
            }
            count = 0;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35872
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>
#include <bitset>
 
using namespace std;

int main(){
    int K;
    string S;
    cin >> K >> S;
    if(S.size()>K){
        cout << S.erase(K) << "..." << endl;
    }
    else{
        cout << S << endl;
    }
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i=0 ; i<n; ++i)
#define rep2(i, j, n) for(int i=j; i<n; ++i)
using namespace std;
typedef long long ll;
typedef unsigned long ul;


int main(){
    ll A, B;
    ll ans=-1;

    cin>>A >> B;
    if(0<A&& A<10 && 0<B && B<10)ans=A*B;   
    cout<<ans<<endl;
}

Measured memory_bytes: 256
def main():
  N, K = map(int,input().split())
  H = list(map(int,input().split()))
  H=sorted(H)
  if N<K:
    print(0)
    return
  elif K!=0:
    print(sum(H[:-K]))
  else:
    print(sum(H))

if __name__ == '__main__':
    main()

Measured memory_bytes: 26024
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=2147483646;
int fb;
struct tree{
	int h[60],nex[110],to[110],M;
	void reset(){
		M=0;
		memset(h,0,sizeof(h));
	}
	void add(int a,int b){
		M++;
		to[M]=b;
		nex[M]=h[a];
		h[a]=M;
	}
	int fa[60];
	void dfs(int x){
		for(int i=h[x];i;i=nex[i]){
			if(to[i]!=fa[x]&&to[i]!=fb){
				fa[to[i]]=x;
				dfs(to[i]);
			}
		}
	}
}a,b;
int d[60],v[60],n,M;
bool f[60];
void dfs(int fa,int x){
	int i,tm;
	tm=++M;
	f[x]=1;
	for(i=a.h[x];i;i=a.nex[i])v[a.to[i]]=tm;
	for(i=b.h[x];i;i=b.nex[i]){
		if(b.to[i]!=fa&&v[b.to[i]]==tm&&b.to[i]!=fb)dfs(x,b.to[i]);
	}
}
struct graph{
	int h[60],nex[110],to[110],M;
	bool v[60],ins[60];
	void reset(){
		M=0;
		memset(h,0,sizeof(h));
		memset(v,0,sizeof(v));
		memset(ins,0,sizeof(ins));
	}
	void add(int a,int b){
		M++;
		to[M]=b;
		nex[M]=h[a];
		h[a]=M;
	}
	bool dfs(int x){
		v[x]=1;
		ins[x]=1;
		for(int i=h[x];i;i=nex[i]){
			if(!v[to[i]]){
				if(!dfs(to[i]))return 0;
			}else if(ins[to[i]])
				return 0;
		}
		ins[x]=0;
		return 1;
	}
}g;
int solve(int r){
	fb=r;
	int i,cnt;
	memset(a.fa,0,sizeof(a.fa));
	a.dfs(r);
	memset(b.fa,0,sizeof(b.fa));
	b.dfs(r);
	memset(f,0,sizeof(f));
	dfs(0,r);
	g.reset();
	cnt=0;
	for(i=1;i<=n;i++){
		if(!f[i]){
			if(!f[a.fa[i]])g.add(i,a.fa[i]);
			if(!f[b.fa[i]])g.add(b.fa[i],i);
			cnt++;
		}
	}
	for(i=1;i<=n;i++){
		if(!g.dfs(i))return inf;
	}
	return cnt;
}
void work(){
	int i,j,x,y,ans;
	scanf("%d",&n);
	a.reset();
	b.reset();
	memset(d,0,sizeof(d));
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		a.add(x,y);
		a.add(y,x);
		d[x]++;
		d[y]++;
	}
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		b.add(x,y);
		b.add(y,x);
	}
	ans=inf;
	for(i=1;i<=n;i++)ans=min(ans,solve(i));
	for(i=1;i<=n;i++){
		if(d[i]==1){
			for(j=1;j<=n;j++){
				if(j!=i){
					x=a.to[a.h[i]];
					a.to[a.h[i]]=j;
					ans=min(ans,solve(i)+1);
					a.to[a.h[i]]=x;
				}
			}
		}
	}
	if(ans==inf)ans=-1;
	printf("%d\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}

Measured memory_bytes: 128
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation, std::lower_bound
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>
#include <cmath> // std::atan2
#include <deque>
#include <queue>

using namespace std;
typedef long long ll;
#define INF 1999999999
#define MODA 1000000007 
#define rep(i,n) for (long long i = 0; i < (n); ++i)

int main() {
  ll N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<ll> l(Q), r(Q);
  rep(i, Q) cin >> l[i] >> r[i];

  vector<ll> ACcount(N, 0);
  for (ll i = 1; i < N; ++i) {
    if(S[i-1] == 'A' && S[i] == 'C') {
      ACcount[i] = ACcount[i-1] + 1;
    }
    else {
      ACcount[i] = ACcount[i-1];
    }
  }  
  rep(i, Q) {
    ll count = 0;
    count = ACcount[r[i]-1] - ACcount[l[i]-1];
    cout << count << endl;
  }
  return 0;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,mn;
  int a[1000];
  while(1){
    cin>>n;
    if(n==0) break;
    for(int i=0;i<1000;i++){
      a[i]=0;
    }
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    sort(a,a+n);
    mn=1000000;
    for(int i=0;i<n-1;i++){
      mn=min(mn,a[i+1]-a[i]);
    }
    cout<<mn<<endl;
  }
  return 0;
}



Measured memory_bytes: 3124
function Main(input) {
  var inputs = input.split(' ')
  var code = parseInt(inputs[0])
  var zissou = parseInt(inputs[1])
  var result = 0
  switch (code) {
    case 1:
      result += 300000
      break
    case 2:
      result += 200000
      break
    case 3:
      result += 100000
      break
    default:
  }
  switch (zissou) {
    case 1:
      result += 300000
      break
    case 2:
      result += 200000
      break
    case 3:
      result += 100000
      break
    default:
  }
  if (code == 1 && zissou == 1) {
    result += 400000
  }
  console.log(result)
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, Max, a[MAXN], b[MAXN];
bool dp[MAXN][MAXN][MAXN], vis[MAXN];
void dodp() {
	for (int l = 1; l <= Max; l++) {
		for (int i = 0; i <= Max; i++)
		for (int j = 0; j <= Max; j++) {
			dp[l][i][j] = dp[l - 1][i][j];
			if (vis[l]) dp[l][i][j] |= dp[l][i % l][j];
		}
	}
}
int main() {
	Max = 50;
	for (int i = 0; i <= Max; i++)
		dp[0][i][i] = vis[i] = true;
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	for (int i = 1; i <= n; i++)
		read(b[i]);
	dodp();
	for (int i = 1; i <= n; i++)
		if (!dp[Max][a[i]][b[i]]) {
			puts("-1");
			return 0;
		}
	ll ans = 0;
	for (int p = Max; p >= 1; p--) {
		vis[p] = false, dodp();
		bool skip = true;
		for (int i = 1; i <= n; i++)
			if (!dp[Max][a[i]][b[i]]) skip = false;
		if (!skip) {
			ans += 1ll << p;
			vis[p] = true;
		}
	}
	writeln(ans);
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main()
{
  	//文字a～zを表示
    char c;
  	//フラグ（フラグの和が最大が求めるもの）
	int flag[25];
  	//for文用のカウンタ
	int count;
  	//出力用の答え
  	int answer;
  	//二つに分かれた文字列
  	std::string target1,target2;
  	//入力値
  	int N;
  	std::string S;
  	//flagのアレイからアレイの和を求める
  	int sum;
 
  	cin >> N >> S;
  	
  	//answerの初期値の設定
  	answer = 0;
  	
  	for(int j = 0 ; j < N ; j++ ){
      	
      	//各文字分割パターンを確かめる
  		target1 = S.substr( 0, j );
  		target2 = S.substr( j, N );
  		
      	//カウンタの初期化
  		count = 0;
      	//sumの初期化
      	sum = 0;
      	//フラグの初期化
      	flag[25] = {0};
    
        for (c = 'a'; c <= 'z'; c++) {

          if( target1.find(c) != string::npos && target2.find(c) != string::npos ){

                //flag[count] = 1; 
				sum += 1;
              
            }

            count++; 

        }
      	
      	//配列の総和を求める
        //sum = 0; 

      	//for(int k = 0; k < count; k++){
        
        //	sum += flag[k];
        
        //}

      	if(sum > answer){
        	
          	answer = sum;
          
        }      
      	
    }

  	cout << answer << endl;

}

Measured memory_bytes: 256
a,b = map(int,input().split())

k1 = a + b
k2 = a - b
k3 = a * b

if k1 > k2 :
    if k1 > k3 :
        print(k1)
    else :
        print(k3)
elif k2 > k3:
        print(k2)
else :
        print(k3)

Measured memory_bytes: 3060
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define all(v) (v).begin(),v.end()
#define fi first
#define se second
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
using Pc=pair<char,char>;
ll dp[300][200000];
map<int,ll> mp;
int main() {
 ll n,m;
 cin>>n>>m;
 ll x=max(n,m),y=min(n,m);
 ll cnt_x=0,cnt_y=0;
 //ll cnt=0;
 while(!(x==1&&y==0)&&!(x==1&&y==1)&&!(x==0&&y==0)&&!(x==0&&y==1)){
     if(x>y){
         y+=(x/2);
         cnt_x+=(x/2);
         x%=2;
     }
     else{
         x+=(y/2);
         cnt_y+=(y/2);
         y%=2;
     }
 }
// cout<<cnt_x<<" "<<cnt_y<<endl;
 ll res=(cnt_x^cnt_y);
if(res!=0)cout<<"Alice"<<endl;
else cout<<"Brown"<<endl;
}

Measured memory_bytes: 256
number = list(map(int, input().split()))
n = number[0]
a = number[1]
b = number[2]
total = 0


def test(a):
    t = 0
    while a > 0:
        t += a % 10
        a //= 10

    return t


for i in range(1, n + 1):
    c = test(i)
    if c >= a and c <= b:
        total += i

print(total)

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

using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  const double pi = acos(-1);

  int r;
  cin >> r;

  cout << fixed << setprecision(3) << 2 * pi * r << endl;

  return 0;
}


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

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

    long long n, p;
    cin >> n >> p;

    for(long long g = pow(p, 1.0 / n) + 1; g >= 1; g--){
        if(p % (long long)(pow(g, n)) == 0){
            cout << g << endl;
            return 0;
        }
    }

    return 0;
}

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

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> c(H);
    for(auto &e : c) cin >> e;
    int ans = 0;
    rep(S, 1 << H) rep(T, 1 << W) {
        bitset<20> bh(S), bw(T);
        int cnt = 0;
        rep(i, H) rep(j, W) {
            if(bh[i]|| bw[j]) continue;
            if(c[i][j] == '#') cnt++;
        }
        if(cnt == K) ans++;
    }
    cout << ans << '\n';
    return 0;
}


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

int XXX;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];

    immutable int X = 9;
    auto G = new int[][](N+1);

    foreach (x; 0..X) {
        if ((1 << x) > N) break;
        foreach (i; 1..N+1) {
            if ((i & (1 << x)) && i != (1 << x)) {
                G[1<<x] ~= i;
            }
        }
    }

    int sm = 0;
    foreach (i; 1..N+1) {
        G[i] = G[i].sort().uniq.array;
        sm += G[i].length.to!int;
    }

    sm.writeln;
    foreach (i; 0..N) {
        foreach (j; G[i]) {
            writeln(i, " ", j);
        }
    }
    stdout.flush;


    int ask(int n) {
        debug {
            if (n == XXX) {
                writeln(n, " ", "OK");
                return 2;
            } else if (G[n].canFind(XXX) || G[XXX].canFind(n)) {
                return 1;
            } else {
                return 0;
            }
        }

        writeln(n);
        stdout.flush;


        auto s = readln.chomp;
        if (s == "Yes") {
            return 2;
        } else if (s == "Near") {
            return 1;
        } else {
            return 0;
        }
    }



    while (K--) {
        debug {
            XXX = readln.chomp.to!int;
        }
        int ans = 0;
        bool ok = false;
        foreach (x; 0..X) {
            int res = (1<<x) <= N ? ask(1<<x) : 0;
            if (res == 2) {
                ok = true;
                break;
            } else if (res == 1) {
                ans |= (1 << x);
            }
        }
        if (!ok) {
            ask(ans);
        }
    }
}



Measured memory_bytes: 3312
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<ll,pll> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Segment_Tree{
	private:
	int n;
	vl date,lazy;
	void Set_Lazy(int k,ll x){
		(date[k]*=x)%=mod;
		(lazy[k]*=x)%=mod;
	}
	void Push(int k){
		Set_Lazy(k*2+1,lazy[k]);
		Set_Lazy(k*2+2,lazy[k]);
		lazy[k]=1;
	}
	void Fix(int k){
		date[k]=(date[k*2+1]+date[k*2+2])%mod;
	}
	void rec(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return;
		if(a<=l&&r<=b){
			Set_Lazy(k,2);
			return;
		}
		int m=(l+r)/2;
		Push(k);
		rec(a,b,k*2+1,l,m);
		rec(a,b,k*2+2,m,r);
		Fix(k);
	}
	ll Rec(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return date[k];
		int m=(l+r)/2;
		Push(k);
		return (Rec(a,b,k*2+1,l,m)+Rec(a,b,k*2+2,m,r))%mod;
	}
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=lazy=vl(2*n-1);
		fill(lazy.begin(),lazy.end(),1);
	}
	void Update(int k,int x){
		k+=n-1;
		(date[k]+=x)%=mod;
		while(k>0){
			k=(k-1)/2;
			Fix(k);
		}
	}
	void Mul(int a,int b){
		rec(a,b,0,0,n);
	}
	ll Query(int a,int b){
		return Rec(a,b,0,0,n);
	}
	ll Open(int k){
		for(auto i:date) cout<<i<<' ';cout<<endl;
		for(auto i:lazy) cout<<i<<' ';cout<<endl;
		return date[k+n-1];
	}
};
 
int n;
vi l,r,a;
vp a_;
 
vi f(){
	vi c(n);
	vp b;
	for(int i=0;i<n;i++){
		if(b.empty()||b.back().first<a[i]) b.push_back({a[i],i});
		auto it=lower_bound(b.begin(),b.end(),make_pair(a[i],i));
		c[i]=it->second;
	}
	reverse(a.begin(),a.end());
	for(int i=0;i<n;i++) a[i]*=-1;
	return c;
}
 
int main(){
	cin>>n;
	a=l=r=vi(n);
	a_=vp(n);
	for(int i=0;i<n;i++) cin>>a_[i].second>>a_[i].first;
	sort(a_.begin(),a_.end());
	for(int i=0;i<n;i++) a[i]=a_[i].second;
	l=f();r=f();
	reverse(r.begin(),r.end());
	for(int i=0;i<n;i++) r[i]=n-r[i]-1;
	vvi g(n+2);
	for(int i=0;i<n;i++) g[r[i]+2].push_back(l[i]);
	Segment_Tree st(n+1);
	st.Update(0,1);
	ll res=1;
	for(int i=0;i<n;i++) (res*=2)%=mod;
	for(int i=1;i<=n;i++){
		for(auto j:g[i]){
			st.Mul(0,j+1);
		}
		ll tmp=st.Query(0,i)*(mod-1)%mod;
		st.Update(i,tmp);
	}
	for(auto i:g[n+1]) st.Mul(0,i+1);
	cout<<(st.Query(0,n+1))%mod<<endl;
}

Measured memory_bytes: 23320
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i=0;i<(n);i++)
#define REP1(i,n) for(long long i=1;i<=(n);i++)
#define REP2D(i,j,h,w) for(long long i=0;i<(h);i++) for(long long j=0;j<(w);j++)
#define REP2D1(i,j,h,w) for(long long i=1;i<=(h);i++) for(long long j=1;j<=(w);j++)
#define PER(i,n) for(long long i=((n)-1);i>=0;i--)
#define PER1(i,n) for(long long i=(n);i>0;i--)
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define FORE(i,a,b) for(long long i=(a);i<=(b);i++)
#define ITE(arr) for(auto ite=(arr).begin();ite!=(arr).end();++ite)
#define ALL(a) ((a).begin()),((a).end())
#define RANGE(a) (a),((a)+sizeof(a))
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define YNPRT(b) cout<<((b)?"Yes":"No")<<endl
#define ENTER printf("\n")
#define REV(arr) reverse(ALL(arr))
#define PRT(a) cout<<(a)<<endl
#ifdef DEBUG
#define DBPRT(a) cout << "[Debug] - " << #a << " : " << (a) << endl
#define DBSTART if(1){
#define DBEND }
#else
#define DBPRT(a) do{}while(0)
#define DBSTART if(0){
#define DBEND }
#endif
#define PRTLST(arr,num) REP(_i,num) cout<<_i<<" - "<<arr[_i]<<endl;
#define PRTLST2(arr2,d1,d2) REP(_i,d1) REP(_j,d2) cout<<_i<<","<<_j<<" : "<<arr2[_i][_j]<<endl;
#define PRTLST2D(arr2,d1,d2) do{cout<<"L\t";REP(_i,d2) cout<<_i<<"\t"; cout<<endl; REP(_i,d1){cout<<_i<<"\t";REP(_j,d2){cout<<arr2[_i][_j]<<"\t";}cout<<endl;}}while(0);

#define TOSUM(arr,sum,n) {sum[0]=arr[0];REP1(i,n-1) sum[i]=sum[i-1]+arr[i];}

#define MIN(target,v1) (target)=min(target,v1)
#define MAX(target,v1) (target)=max(target,v1) 
#define P1 first
#define P2 second
#define PB push_back
#define UB upper_bound
#define LB lower_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;
const int Move[4][2] = {-1,0,0,1,1,0,0,-1};
const int Move_[8][2] = {-1,0,-1,-1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p) {os<<"( "<<p.P1<<" , "<<p.P2<<" )";return os;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {ITE(v) os << (ite-v.begin()) << " : " << *ite <<endl;return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v) {os<<" { ";ITE(v) {os<<*ite;if(ite!=--v.end()){os<<" , ";}} os<<" } ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& m) {ITE(m) {os<<ite->P1<<"\t\t|->\t\t"<<ite->P2<<endl;} return os;}

//---------------------
#define MAXN 100000
//---------------------

ll a,b;

int main(){
	cin >> a >> b;
	PRT(max(0ll,a-2*b));
	return 0;
}









Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int first, last ,num, i;
	i = 0;
	scanf("%d%d%d",&first, &last, &num);
	for(first;first <= last;first++){
		if(num%first == 0)
			i++;
	}
	printf("%d\n",i);

	return 0;
}

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

int main() {
	int a, b, n;
	while (cin >> a >> b >> n) {
		int ans = 0;
		for (int i = 0;i < n;i++) {
			ans += ((a%b) * 10 / b);
			a *= 10;
			a %= b;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
 
int main() {
  int n, sum=0;
  vector<int> v(n);
  vector<int> c(n);
  cin>>n;
  rep(i,n) cin>>v[i];
  rep(i,n) cin>>c[i];
  rep(i,n) {
    if (v[i]>c[i]) sum += v[i]-c[i];
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 512
n,t=map(int,input().split())
ct=[list(map(int,input().split())) for i in range(n)]
flag=0
ans=ct[0][0]
for i in range(n):
    if ct[i][1]<=t:
        flag=1
        ans=min(ans,ct[i][0])
    else:
        pass
if flag==0:
    print("TLE")
else:
    print(ans)

Measured memory_bytes: 9196
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main(){
	int n,m,p;
	while(1){
		cin>>n>>m>>p;
		if(n+m+p==0) break;
		int sum=0,win;
		rep(i,1,n+1){
			int a;
			cin>>a;
			sum+=a;
			if(i==m) win=a;
		}
		o((win==0?0:(100-p)*sum/win));
	}
}

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

int main(){
  int n;
  cin >> n;
  string s;
  map<string,int> mp;
  int maxV = 0;
  for ( int i = 0; i < n; i++){
    cin >> s;
    mp[s]++;
    maxV = max(maxV, mp[s]);
  }
  for ( map<string,int>::iterator it = mp.begin(); it != mp.end(); it++){
    if(it->second == maxV){
      cout << it->first << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <vector>
#include <functional>

struct Query {
    int a, b, c, d;
};

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<Query> qs(q);
    for (auto& p : qs) {
        std::cin >> p.a >> p.b >> p.c >> p.d;
        --p.a, --p.b;
    }

    int ans = 0;
    std::vector<int> xs(n);
    std::function<void(int, int)>
        dfs = [&](int i, int p) -> void {
        if (i == n) {
            int score = 0;
            for (const auto& p : qs) {
                if (xs[p.b] - xs[p.a] != p.c) continue;
                score += p.d;
            }
            ans = std::max(ans, score);

        } else {
            for (int d = p; d <= m; ++d) {
                xs[i] = d;
                dfs(i + 1, d);
            }
        }
    };

    dfs(0, 1);
    std::cout << ans << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>
#include <iterator>
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
constexpr ll mop = 1000000007;
constexpr ll mop2 = 998244353;

using namespace std;

constexpr ll NOT_SPECIFIED_VALUE_MIN = INT64_MIN;
constexpr ll NOT_SPECIFIED_VALUE_MAX = INT64_MAX;

template <typename T>
T gcd(T a, T b) {
	if (a < b) gcd(b, a);
	T r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}

template <typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

int main() {
	ll a, b;
	a = b = -1;
	while (true) {
		cin >> a >> b;
		if (a == -1) { break; }
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
		a = b = -1;
	}
}



Measured memory_bytes: 2984
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
	int n,p;
	int stone[50];
	
	cin>> n >> p;
	
	while ( n+p > 0)
	{
		int bowl = p;
		memset(stone,0,sizeof(stone));
		for (int i=0;i<1000000;++i)
		{
			if (stone[i % n] == p) 
			{
				cout << (i%n) << endl;
				break;
			}
			
			if (bowl > 0) 
			{
				++stone[i%n];
				--bowl;
			}
			else if (stone[i%n] > 0)
			{
				bowl = stone[i%n];
				stone[i%n] = 0;
			}
			
		}
		
		cin>> n >> p;
	}
}

Measured memory_bytes: 868
#include <bits/stdc++.h>
using namespace std;
int n, i, m, j, k, s, a;
int main(){
	scanf("%d", &n);
	n=n%10;
	if(n==2 || n==4 || n==5 || n==7 || n==9){
		printf("hon");
	}
	else if(n==0 || n==1 || n==6 || n==8){
		printf("pon");
	}
	else if(n==3){
		printf("bon");
	}
}

Measured memory_bytes: 3824
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
typedef long long ll;
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
// #define rep(i,n) for(i,0,n)
 
int main() {
	// 入力
    int N;
    cin >> N;
    int A[N+2];
    A[0] = 0;
    for (int i = 1; i < N+1; ++i) cin >> A[i];
    A[N+1] = 0;
 
 
	ll sum = 0;
    for (int i = 1; i < N+2; ++i) sum += abs(A[i] - A[i-1]);
    // cout << "sum " << sum << endl;
	ll dist[N];
	for (int i = 0; i < N; ++i){
		if (A[i]<A[i+1] && A[i+2]<A[i+1]){
			if (A[i]<A[i+2]) dist[i] = A[i+1] - A[i+2];
			else dist[i] = A[i+1] - A[i];
		}
		else if (A[i]>A[i+1] && A[i+2]>A[i+1]){
			if (A[i]<A[i+2]) dist[i] = A[i] - A[i+1];
			else dist[i] = A[i+2] - A[i+1];
		}
		else{
			dist[i] = 0;
		}
	}

    // for (int i = 0; i < N; ++i) cout << 2*dist[i] << endl;
    for (int i = 0; i < N; ++i) cout << sum - 2 * dist[i] << endl;
}
 


Measured memory_bytes: 2432