akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define MOD 1000000007
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans;
int N,Q;
vi A, M;

bool canMake(int id, int m){
    if(m == 0) return true;
    if(id >= N) return false;

    bool res = canMake(id+1, m - A[id]) || canMake(id+1, m);
    return res;
}

void solve(){
    rep(i, Q){
        if(canMake(0, M[i])) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

int main(){
    cin >> N;
    A.resize(N);
    rep(i, N) cin >> A[i];

    cin >> Q;
    M.resize(Q);
    rep(i, Q) cin >> M[i];

    solve();
}



Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  string n;
  cin>>n;
  if(n[0]=='7'||n[1]=='7'||n[2]=='7')
    cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main(int argc, char const *argv[])
{
    int N, M, X, Y;
    vector<int> xi;
    vector<int> yi;
    cin >> N >> M >> X >> Y;

    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        xi.push_back(tmp);
    }
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        yi.push_back(tmp);
    }

    sort(xi.begin(), xi.end());
    sort(yi.begin(), yi.end());

    if (xi[N - 1] < yi[0] && X < yi[0] && xi[N - 1] < Y)
    {
        cout << "No War" << endl;
    }
    else
    {
        cout << "War" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<set>
#include<iomanip>
#define rep(i,n) for(ll i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<double,double>P;

int main()
{
    ll x,y;
    cin>>x>>y;
    ll ans=0;
   
    if(x<y)
    {
        ans=min(abs(y-x),abs(y-abs(x))+1);
    }
    else
    {
        ans=min(abs(y-x)+2,abs(x+y)+1);
    }
    
    cout<<ans;
    
    
}

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

#define DEBUG(x) cout << #x << ": " << x << endl;
#define DEBUG_VEC(v)                                      \
  cout << #v << ":";                                      \
  for (int i = 0; i < v.size(); i++) cout << " " << v[i]; \
  cout << endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int> >
#define vll vector<vector<ll> >
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout << setprecision(15) << fixed << p << endl;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx2[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dy2[8] = {0, 1, 1, 1, 0, -1, -1, -1};


int main(){
  int n, i, j;
  cin >> n;
  vl a(n);
  //vector<pii> b(n);
  vl b(n);
  for (i = 0; i < n; i++) {
    cin >> a[i];
    //b[i].first = a[i];
    //b[i].second = i;
    b[i] = a[i];
  }
  sort(b.begin(), b.end());
  int pre = 0;
  int now = 0;
  for (i = 0; i < n; i++) {
    if (pre >= a[i]) {
      cout << 0 << endl;
      continue;
    }
    ll cnt = 0;
    while (b[now] < a[i]) {
      cnt += (b[now] - pre);
      now++;
    }
    cnt += (a[i] - pre) * (n - now);
    cout << cnt << endl;
    pre = a[i];
  }  
}

/*
2
1 2


10
1 2 1 3 2 4 2 5 8 1
*/


Measured memory_bytes: 2688
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<map>
#include<cmath>
#include<set>
#define ll long long
#define inf 0x7fffffff;
#define maxn 1000005
using namespace std;
int x,y,a,b,c;
ll A[maxn];
int read()
{
    int l=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        w=-1;
        else
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        l*=10;
        l+=ch-'0';
        ch=getchar();
    }
    return l*w;
} 
int main(){
    x=read(),y=read(),a=read(),b=read(),c=read();
    for(int i=0;i<a;i++)
    A[i]=read();
    sort(A,A+a,greater<ll>());
    for(int i=x;i<x+b;i++)
    A[i]=read();
    sort(A+x,A+x+b,greater<ll>());
    for(int i=x+y;i<x+y+c;i++)
    A[i]=read();
    sort(A,A+x+y+c,greater<ll>());
    ll ans=0;
    for(int i=0;i<x+y;i++) ans+=A[i];
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4352
def solve(N, K):
    ans = 0
    k = len([n for n in range(1, N + 1) if n % K == 0])
    ans += k * k * k
    if K % 2 == 0:
        k = len([n for n in range(1, N + 1) if n % K == K // 2])
        ans += k * k * k

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))


Measured memory_bytes: 10936
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();

            int score = 759;
            for (int i = 0; i < S.Length - 2; i++)
            {
                int num = int.Parse((S[i].ToString() + S[i + 1].ToString() + S[i + 2].ToString()));
                int candidate_score = Math.Abs(num - 753);
                if (score > candidate_score) score = candidate_score;

            }
            Console.WriteLine(score);
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>

#define N 100

void dfs(int x, int y, int xs, int ys, char fld[]);

int main(){
    int ys,xs;
    
    
    while (scanf("%d%d", &ys, &xs), ys){
        char field[N*N+1];
        int cnt=0;
        
        for (int i=0; i<ys; i++){
            scanf("%s", field+(i*xs));
        }
        for (int i=0; i<ys; i++){
            for (int j=0; j<xs; j++){
                if (field[j+xs*i]!='.'){
                    dfs(j, i, xs, ys, field);
                    cnt++;
                }
            }
        }    

        printf("%d\n", cnt);
    }
    return 0;
}

void dfs(int x, int y, int xs, int ys, char fld[]){
    char here;
    here = fld[x+xs*y];
    fld[x+xs*y] = '.';
    for (int dx=-1; dx<=1; dx++){
        for (int dy=-1; dy<=1; dy++){
            if (dx*dy!=0) continue;
            int nx = x+dx;
            int ny = y+dy;
            if (nx < 0 || nx >= xs || ny < 0 || ny >=ys) continue;
            if (fld[nx+xs*ny]==here) dfs(nx, ny, xs, ys, fld);
        }
    }
    return;
}

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

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

    int count_white[n];
    if(s[0] == '.'){
        count_white[0] = 1;
    }else{
        count_white[0] = 0;
    }
    for(int i=1; i<n; i++){
        if(s[i] == '.'){
            count_white[i] = count_white[i-1] + 1;
        }else{
            count_white[i] = count_white[i-1];
        }
    }

    int min_num = 1000000;
    for(int i=0; i<n; i++){
        min_num = min(i+1-count_white[i] + count_white[n-1]-count_white[i], min_num);
    }

    min_num = min(min_num, count_white[n-1]);

    cout << min_num << endl;

    return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

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

lli realSum[100100];
lli sum[100100];

void func(long long N, long long Q, std::vector<long long> A){

    REP(i,0,N){
        realSum[i+1] = realSum[i]+A[i];
    }

    vector<lli> v;
    for(lli i=1;i<(N+1)/2;i++){
        lli now = A[N-1-i];
        lli nex = A[N-1-2*i];
        LOG3(i,now,nex);
        v.push_back((now+nex)/2);
    }
    v.push_back(INF);
    v.push_back(0);

    SORT(v);


    //sum
    vector<lli> vv;
    REP(i,0,N){
        if(i%2!=N%2){
            vv.push_back(A[i]);
        }
    }
    REP(i,0,vv.size()){
        sum[i+1] = sum[i] + vv[i];
        LOG3(i,sum[i+1],vv[i]);
    }

    

    REP(_,0,Q){
        lli x;
        cin>>x;
        lli cnt = (lli)(lower_bound(v.begin(),v.end(),x)-v.begin());
        cnt--;
        if(cnt<0)cnt++;
        cnt += (N)/2;

        //cout<<cnt<<endl;

        lli ans = 0;
        ans = realSum[N]-realSum[cnt];

        lli useCnt = cnt - N/2;

        LOG3(ans,useCnt,sum[useCnt]);
        ans += sum[useCnt];
        cout<<ans<<endl;

    }

}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    func(N, Q, std::move(A));
    return 0;
}


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

void nibutan(vector<int> &dp, int le,int ri, int c) {
	if (ri - le==1) {
		dp[ri] = c;
		return;
	}
	if (dp[(ri+le) / 2] < c) {
		nibutan(dp, le, (le + ri) / 2, c);
	}
	else {
		nibutan(dp, (le + ri) / 2, ri, c);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> da(n);
	for (int i = 0;i < n;i++) {
		cin >> da[i];
	}
	vector<int> dp(1);
	dp[0] = da[0];
	int ans = 1;
	for (int i = 1;i < n;i++) {
		if (dp[ans - 1] >= da[i]) {
			dp.push_back(da[i]);
			ans++;
		}
		else {
			nibutan(dp, -1, ans-1, da[i]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1276
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(){
    int n;
    cin>>n;
    V<string> s(n);
    cinf(n,s);
    ll ans=0;
    for(int i=0;i<n;i++) sort(all(s[i]));
    map<string,ll> mp;
    for(int i=0;i<n;i++) mp[s[i]]++;
    for(auto p:mp){
        ll m=p.sc;
        if(m>=2) ans+=m*(m-1)/2;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 18176
from sys import stdin

if __name__ == '__main__':
    N = int( stdin.readline().rstrip() )
    H = [int(x) for x in stdin.readline().rstrip().split()]
    
    H = dict( zip( range(len(H)), H ) )

    maxv = 0
    count = 0
    for i in range( len(H) - 1 ):
        a = H[i]
        b = H[i+1]
        if a >= b:
            count += 1
        else:
            if maxv < count:
                maxv = count
            count = 0
    if maxv < count:
        maxv = count
    print(maxv)

Measured memory_bytes: 20620
from collections import deque

n, q = map(int, input().split())
p_que = deque([])

for _ in range(n):
    name, t = map(str, input().split())
    p_que.append([name, int(t)])

sum_time = 0
while True:
    p = p_que.popleft()
    if p[1] <= q:
        sum_time += p[1]
        print(p[0], sum_time)
    else:
        sum_time += q
        p[1] -= q
        p_que.append(p)
    if len(p_que) == 0:
        break


Measured memory_bytes: 13304
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

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

const ll MOD = ll(1e9) + 7;
const ll INF = LLONG_MAX;
const ll MAX_N = 1 << 12;
const double EPS = 10e-8;
const double PI = 3.14159265359;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)

int main() {
    ll n;
    cin >> n;
    cout << ((n-1)/11)*2+1 + n%11/7 + (n%11==0)<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    unsigned long long A;
    unsigned long long B;
    unsigned long long C;
    unsigned long long D;
    unsigned long long all;
    unsigned long long C_num;
    unsigned long long D_num;
    unsigned long long CD_num;
    unsigned long long lcm;
    unsigned long long gcd;
    unsigned long long tmp;
    unsigned long long tmp_C;
    unsigned long long tmp_D;
    int i;

    scanf("%lld %lld %lld %lld", &A, &B, &C, &D);

    if(C < D) {
        tmp_C = D;
        tmp_D = C;
    } else {
        tmp_C = C;
        tmp_D = D;
    }
    gcd = tmp_C % tmp_D;
    while(gcd != 0) {
        tmp_C = tmp_D;
        tmp_D = gcd;
        gcd = tmp_C % tmp_D;
    }
    gcd = tmp_D;
    lcm = C * D / gcd;

    all = B - A + 1;

    C_num = (B / C) - ((A-1) / C);
    D_num = (B / D) - ((A-1) / D);
    CD_num = (B / lcm) - ((A-1) / lcm);

    //printf("%lld %lld %lld %lld\n", all, C_num, D_num, CD_num);
    printf("%lld\n", all - C_num - D_num + CD_num);

    return 0;
}

Measured memory_bytes: 128
import itertools

N = int(input())
nums = [3, 5, 7]
num_357 = set()

# retrieval
candidates = []
for i in range(3, 10):
    candidates += list(itertools.product(nums, repeat=i))
for c in candidates:
    for n in nums:
        if n not in c:
            break
    else:
        # c contains 3 && 5 && 7
        tmp = 0
        for ind, i in enumerate(c):
            tmp += i * pow(10, ind)
        num_357.add(tmp)

# result
ans = 0
for n_357 in num_357:
    if n_357 <= N:
        ans += 1
print(ans)

Measured memory_bytes: 10124
from collections import Counter


def main():
    n = int(input())
    slist = [list(input()) for _ in range(n)]

    slist2 = [''.join(sorted(s)) for s in slist]
    ans = 0
    counter = Counter(slist2)
    for _, v in counter.items():
        if v > 1:
            ans += v * (v - 1) // 2
    print(ans)


main()


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

int main() {
    int H,W;
    cin >> H >> W;
    vector<string>S(H);
    int ans[55][55];
    for(int i = 0; i < H; i++) {
        cin >> S[i];
    }
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            ans[i][j] = 0;
            if(S[i][j] == '#') {
                continue;
            }
            if(i != 0) {
                if(S[i-1][j] == '#') {
                    ans[i][j]++;
                }
                if(j != 0) {
                    if(S[i-1][j-1] == '#') {
                        ans[i][j]++;
                    }
                }
                if(j != W-1) {
                    if(S[i-1][j+1] == '#') {
                        ans[i][j]++;
                    }
                }
            }
            if(j != 0) {
                if(S[i][j-1] == '#')   ans[i][j]++;
            }
            if(j != W-1) {
                if(S[i][j+1] == '#')   ans[i][j]++;
            }
            if(i != H-1) {
                if(S[i+1][j] == '#')   ans[i][j]++;
                if(j != 0) {
                    if(S[i+1][j-1] == '#') ans[i][j]++;
                }
                if(j != W-1) {
                    if(S[i+1][j+1] == '#') ans[i][j]++;
                }
            }
        }
    }
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(S[i][j] == '#') {
                cout << '#';
            }
            else {
                cout << ans[i][j];
            }
        }
        cout << endl;
    }
}	


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
	priority_queue<int> Q;
	string S;
	while(true)
	{
		cin >> S;
		if (S == "end")
		{
			return 0;
		}
		else
		{
			if (S == "insert")
			{
				int a;
				cin >> a;
				Q.push(a);
			}
			else
			{
				cout << Q.top() << endl;
				Q.pop();
			}
		}
	}
}


Measured memory_bytes: 7044
#include <iostream>
#include <iomanip>


int main () {
  int a, b, c, d, e, f;
  float x, y, temp;
  std::cout << (std::fixed) << std::setprecision(3);
  while (std::cin >> a >> b >> c >> d >> e >>f) {
    y = (c * d - f * a) / (float)(b * d - e * a);
    x = (c - b * y) / (float)a;
    std::cout << x << " " << y << std::endl;
  }
  return 0;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];



void solve() {
  string a;
  // 文字列を一行でinput()
  getline(cin, a);

  for (int i=0; i< a.size(); i++) {
    // 小文字ならば
    if (a[i] >= 'a' && a[i]<= 'z') a[i] = toupper(a[i]); // 大文字に変換
    // 大文字ならば
    else if (a[i] >= 'A' && a[i] <= 'Z') a[i] = tolower(a[i]); // 小文字に変換
  }
  cout << a << endl;

}

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






Measured memory_bytes: 3084
#include <stdio.h>
#include <stdlib.h>
int main() {
    int N,Q;
    char S[100001];
    int counts[100001];//i番目までにACが何回現れたか
    int ans[100001];
    int l, r;
    int count = 0;
    scanf("%d",&N);
    scanf("%d",&Q);
    scanf("%s",S);
    //ACが現れた回数をcountsに保存する
    //forの範囲に注意
    for (int i = 0; i < N - 1; ++i) {
        if (S[i] == 'A' && S[i + 1] == 'C')++count;
        counts[i + 1] = count;
    }
    //答えの計算
    for (int i = 0; i < Q; ++i) {
        scanf("%d",&l);
        scanf("%d",&r);
        ans[i] = counts[r - 1] - counts[l - 1];
    }
    for (int i = 0; i < Q; ++i)
    	printf("%d\n", ans[i]);
}


Measured memory_bytes: 1664
#include <stdio.h>
int main(void){
	int a,b,c,check=0;
	scanf("%d%d%d",&a,&b,&c);
	if((a+b==c)||(b+c==a)||(c+a==b)){
		printf("Yes");
	}else{
		printf("No");
	}
	return 0;
}	


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>

#include <map>
#include <utility>
#include <ctime>
#define INF 999999999
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);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
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool debug=false;
/*---------------------------------------------------*/

int main(){
  int n,sum=1;
  cin>>n;
  while(1){
    if(sum>n)break;
    sum*=2;
  }
  cout<<sum/2<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define F first
#define S second
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

int un[100000];

int find(int x){
  if(x==un[x])return x;
  return un[x]=find(un[x]);
}

int unit(int a,int b){
  un[find(a)]=un[find(b)]=find(a);
}

int b[100000][2];

main(){
  int n;
  while(cin>>n,n){
    rep(i,n)un[i]=i;
    rep(i,n){
      rep(j,2){
	int k;
	cin>>k>>b[i][j];
	unit(i,k);
      }
    }
    map<int,set<int> > group;
    rep(i,n)group[find(i)].insert(i);
    int ans=1;
    FOR(miter,group){
      map<int,int> app;
      FOR(siter,miter->S){
	app[-b[*siter][0]]++;
	app[-b[*siter][1]]++;
      }
      ans=ans*(app.begin()->S/2)%10007;
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1268
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstdio>
using namespace std;
typedef long long ll;

#define _SI(arr) (sizeof(arr)/sizeof(arr[0])

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

	ll sum = 0;

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

	for (ll i = 0; i < N - 1; i++)
	{
		sum += v[i];
	}

	if (sum > v[N - 1]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
#define ll long long
long long df(long long a,long long b)
{
    long long x = a*a + b*b;
    return x;
}
int main()
{
    long long a,b;
    int sum = 0;
    long long x,y;
    scanf("%lld %lld",&a,&b);
    for(int i=1;i<=a;i++)
    {
        scanf("%lld %lld",&x,&y);
        long long f = x*x + y*y;
        long long z = b*b;
        if(f <= z)
            sum++;
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 3800
/* ~created by Pratik~ */

#include <bits/stdc++.h> 
using namespace std; 
  
typedef long long int ll; 
  
int gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
} 
ll findlcm(ll arr[], ll n) 
{ 
    ll ans = arr[0]; 
  
    for (int i = 1; i < n; i++) 
        ans = (((arr[i] * ans)) / 
                (gcd(arr[i], ans))); 
    return ans; 
} 
int main()
{
	int n,m,i;
	cin>>n>>m;
	ll a[n],b[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		b[i]=a[i]/2;
	}
	ll c1=0,c=0,tmp=a[0],val=0;
	while((tmp%2==0)&&(tmp>0))
	{
		c1++;
		tmp/=2;
	}
	for(i=0;i<n;i++)
	{
		c=0;
		tmp=a[i];
		while((tmp%2==0)&&(tmp>0))
		{
			c++;
			tmp/=2;
		}
		// cout<<a[i]<<" "<<c<<" "<<c1<<endl;
		if(c==c1) val++;
	}
	if(val!=n) cout<<0<<endl;
	else
	{
		ll lc=findlcm(b,n);
		// cout<<lc<<endl;
		ll ans=m/lc;
		if(ans%2==0)
			ans/=2;
		else 
			ans=ans/2+1;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<set>
#define lli long long int
using namespace std;
int main()
{
	lli r,g,b,k;
	cin>>r>>g>>b;
	cin>>k;
	while(k){
		if(b<=g)
		{
			b=b*2;
			k--;
		}
		else if(g<=r){
			g=g*2;
			k--;
		}
		else{
			b=b*2;
			k--;
		}
	}
	if(g>r&&b>g)
	cout<<"Yes";
	else
	cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ull = unsigned long long int;
using ll = long long int;

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long m = max(a * c, a * d);
    m = max(m, b * c);
    m = max(m, b * d);
    cout << m << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

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

    string s;
    cin >> s;
    for (int i = 0; i < (int)s.size(); i++) {
    	if (i % 2 == 0 && s[i] == 'L') {
    		cout << "No" << endl;
    		exit(0);
    	}
    	if (i % 2 == 1 && s[i] == 'R') {
    		cout << "No" << endl;
    		exit(0);
    	}
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
namespace 私が灰コーダーです{
    class Inonoa{
        static void Main(){
            List<int> points = new List<int>(); // aが全部挿入されていくやつ
            long b = 0; // bがどんどん足されていくやつ

            int q = int.Parse(Console.ReadLine()); // Q

            long v = 0; // |x-a|の部分の最小値。更新クエリごとに少しずつずれる

            for(int i=0;i<q;i++){
                string[] qr = Console.ReadLine().Split();
                if(qr[0]=="1"){ // 更新クエリの場合
                    int a = int.Parse(qr[1]);

                    //初めの一回は別
                    if(points.Count!=0){
                        //vを更新したいが、
                        //元のグラフの形状や、元のグラフの最小値を取るxと今のaの大小関係によって更新方法が変わると考えた
                        if(points.Count%2==0){
                            if(a<points[(points.Count-1)/2]){
                                v += Math.Abs(points[(points.Count-1)/2]-a);
                            }else if(a>points[(points.Count+1)/2]){
                                v += Math.Abs(points[(points.Count+1)/2]-a);
                            }
                        }else{
                            v += Math.Abs(points[(points.Count-1)/2]-a);
                        }

                        // aをpointsに挿入するのに挿入位置が分からないので二分探索と言うべきか分からない何かをやった
                        int lft = 0;
                        int rgt = points.Count;

                        while(lft<rgt){
                            int c = points[(lft+rgt)/2];
                            if(a<c){
                                rgt = (lft+rgt)/2;
                            }else if(a>c){
                                lft = (lft+rgt)/2 + 1;
                            }else{
                                lft = (lft+rgt)/2;
                                break;
                            }
                        }
                        points.Insert(lft,a);
                    }else{ //初めの一回、vは0のままですよね…？
                        points.Add(a);
                    }
                    b += int.Parse(qr[2]);

                }else{ //求値
                    Console.Write(points[(points.Count-1)/2]);
                    Console.Write(" ");
                    Console.Write(v+b);
                    Console.Write("\n");
                }
            }
        }
    }
}

Measured memory_bytes: 18604
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define forn(i,n) for(int i=0;i<n;i++)
#define M 1000000007
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)

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

int mod(long long x) {
	return ((x % M + M) % M);
}
int add(int a, int b) {
	return mod(mod(a) + mod(b));
}
int diff(int a, int b) {
	return mod(mod(a) - mod(b));
}

int mul(int a, int b) {
	return mod(mod(a) * mod(b));
}

int modPow(int a, int b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a % M;
	int res = 1;
	while (b) {
		if (b % 2 == 1)
			res = mul(res, a);
		a = mul(a, a);
		b = b / 2;
	}
	return res;
}

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

void solve() {

	string s, t;
	cin >> s >> t;
	int n = s.size();
	int m = t.size();

	int st = 0;
	int ans = INT_MAX;



	while (st <= n - m) {
		int cnt = 0;
		for (int e = 0; e < m; e++) {
			if (s[e + st] != t[e]) {

				cnt++;
			}

		}
		ans = min(ans, cnt);
		st++;
	}

	cout << ans << endl;

}



int32_t main() {

	fastio;

#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif

	// int t; cin >> t;/
	int t = 1;

	while (t--) {
		solve();
	}

	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	string s;cin >> s;
	int x = 0, ma = 0;
	rep(i,n){
		if(s.at(i) == 'I') x++;
		else x--;
		ma = max(ma, x);
	}
	cout << ma << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	double x[4],y[4], p1, p2;
	while( scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
		&x[0], &y[0], &x[1], &y[1], &x[2], &y[2], &x[3], &y[3])!=EOF ) {
		if ( (x[1]-x[0])*(x[3]-x[2])+(y[1]-y[0])*(y[3]-y[2]) == 0.000000) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
  int a, b, x;
  cin >> a >> b >> x;
  if(a <= x && x <= a + b){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var list = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToList();
            list.Reverse();
            for (int i = 0; i < list.Count - 1; i++)
            {
                if (list[i] > list[i + 1] || list[i] == list[i + 1]) continue;
                list[i + 1]--;
                if (list[i] == list[i + 1]) continue;
                Console.WriteLine("No");
                return;
            }
            Console.WriteLine("Yes");
        }
    }
}


Measured memory_bytes: 25820
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main(){
  int n;
  cin >> n;
  vector<int> vec(100002, 0);
  rep(i, n){
    int num;
    cin >> num;
    vec[num]++; vec[num+1]++; vec[num+2]++;
  }
  int biggest = 0;
  rep(i, 100002) biggest = max(biggest, vec[i]);
  cout << biggest << endl;
  return 0;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int main() {
    string s;
    cin >> s;
    if ((int)s.length() >= 4 && s.substr(0, 4) == "YAKI") {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

set<int> st = { 'A', 'C', 'G', 'T' };

int main(void) {
  string S;
  cin >> S;

  int ans = 0;
  REP(i, 0, S.length()) {
    REP(j, i, S.length() + 1) {
      bool ok = true;
      REP(k, i, j) ok = ok && st.count(S[k]);
      if (ok) ans = max(ans, j - i);
    }
  }
  cout << ans << endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  int c, d;
  c = ( a + b ) * 10 / 2;
  d = c / 10;
  if (c % 10 > 4) {
    d++;
  }
  cout << d << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

using namespace std;

int e;

int main()
{
	while (true)
	{
		scanf("%d", &e);

		if (e == 0) break;

		int ret = 999999999;

		for (int y = 0; y * y <= e; y++)
		{
			for (int z = 0; y * y + z * z * z <= e; z++)
			{
				int x = e - (y * y + z * z * z);

				ret = min(ret, x + y + z);
			}
		}

		printf("%d\n", ret);
	}
}

Measured memory_bytes: 2680
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    edges[a].append((b, c))
    edges[b].append((a, c))

Q, K = map(int, readline().split())

dist = [0] * (N + 1)


def dfs(v, p, d):
    dist[v] = d

    for n, dd in edges[v]:
        if n == p:
            continue
        dfs(n, v, d + dd)


dfs(K, -1, 0)

for _ in range(Q):
    x, y = map(int, readline().split())
    print(dist[x] + dist[y])


Measured memory_bytes: 131736
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n,k;cin >> n>> k;
    vl a(n);rep(i,n)cin >> a[i];
    ll t=a[0];
    rep(i,n)t=__gcd(t,a[i]);
    if(k>*max_element(all(a)))cout <<"IMPOSSIBLE"<<endl,exit(0);
    if(k%t==0)cout << "POSSIBLE" <<endl;
    else cout <<"IMPOSSIBLE"<<endl,exit(0);
}   

Measured memory_bytes: 4288
from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=list(map(int,input().split()))
    B=copy(A)
    cnt=0
    for i in range(N):
        if A[i]<0:
            cnt+=1
            B[i]=(-1)*A[i]
    B.sort()
    ans=sum(B)
    if cnt%2==1:
        ans-=B[0]*2
    
    print(ans)

    
resolve()

Measured memory_bytes: 60940
#include <iostream>
#include <cstring>

using namespace std;

#define N 10100
#define MAX_D 128
#define M 1000000007LL

inline long long MOD (long long x){
    if (x < M)
        return x;
    return x - M;
}
string s;
long long d[N][MAX_D][2];
int n, D, i, j, c, C;

int main (){
    cin >> s >> D;
    n = s.size();

    d[0][0][0] = 1;
    ++n;
    for (i = 1; i < n; ++i){
        C = s[i - 1] - '0';
        for (j = 0; j < D; ++j){
            for (c = 0; c < 10; ++c)
                d[i][(j + c) % D][1] = MOD(d[i][(j + c) % D][1] + d[i - 1][j][1]);

            for (c = 0; c < C; ++c)
                d[i][(j + c) % D][1] = MOD (d[i][(j + c) % D][1] + d[i - 1][j][0]);

            d[i][(j + C) % D][0] = MOD (d[i][(j + C) % D][0] + d[i - 1][j][0]);
        }
    }
    --n;
    cout << MOD (d[n][0][0] + d[n][0][1] + M - 1);

    return 0;
}


Measured memory_bytes: 20224
using System;
namespace kozaiyApp
{
    public class MultipleClocks
    {
        static void Main()
        {
            ulong N = ulong.Parse(Console.ReadLine());
            ulong[] T = new ulong[N];

            ulong m = ulong.Parse(Console.ReadLine());
            ulong n;

            // 最小公倍数を求めていく
            for (ulong i = 0; i < N - 1; i++)
            {
                n = ulong.Parse(Console.ReadLine());
                m = LeastCommonMultiple(m, n);
            }

            Console.WriteLine(m);
        }

        // 最大公約数 m > n ユークリッドの互除法 
        public static ulong GreatestCommonDivisor(ulong m, ulong n)
        {
            ulong i;
            while (m % n != 0)
            {
                i = n;
                n = m % n;
                m = i;
            }
            return n;
        }

        // 最小公倍数 m > n
        public static ulong LeastCommonMultiple(ulong m, ulong n)
        {
            return m / GreatestCommonDivisor(m, n) * n;
        }
    }
}


Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();
        int count = 0;
        for(int x = 0 ;x<=k;x++){
            for(int y = 0 ;y<=k;y++){
                if(s-x-y>=0&&s-x-y<=k) count++;
            }
        }
        System.out.println(count);
    }
}

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

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

    vector<int>a(n);
    vector<int>aa(n-1);

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

    for(int i=0; i<n-1; i++){
        if(a[i+1]>a[i]){
            aa[i]=1;
        } else if(a[i+1]==a[i]) {
            aa[i]=2;
        } else {
            aa[i]=3;
        }
    }

    long long y=1000, k=0;

    for(int i=0; i<n-1; i++){
        if(aa[i]==1){
            k += y/a[i];
            y -= a[i]*(y/a[i]);
        } 
        if(aa[i]==3){
            y += k*a[i];
            k=0;
        }
    }

    y += k*a[n-1];

    cout << y << endl;

    return 0;
}


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

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

    vector<string> c(h);
    rep(i,h) {
        cin >> c.at(i);
    }

    rep(i,h) {
        cout << c.at(i) << endl;
        cout << c.at(i) << endl;
    }

    return 0;
}

Measured memory_bytes: 3624
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string s, t;
  cin >> s >> t;
  int r = 1001;
  F0R(i, s.size() - t.size() + 1) {
    int sc = 0;
    F0R(j, t.size()) {
      if (t[j] != s[i + j]) sc++;
    }
    chmin(r, sc);
  }
  cout << r;
}
#endif


Measured memory_bytes: 3656
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n,a,b;
	std::cin >> n >> a >> b;
	int y = std::min(std::max(a-1,b-1),std::max(n-a,n-b));
	if((b-a)%2==0) {
		int x = (b-a)/2;
		print(std::min(x,y));
	} else {
		int z = std::min(a+(b-a)/2,n-b+1+(b-a)/2);
		print(std::min(y,z));
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> as(n);
    vector<pair<int, int>> bcs(m);
    for (int i = 0; i < n; ++i) {
        cin >> as[i];
    }

    for (int i = 0; i < m; ++i) {
        int b, c;
        cin >> b >> c;
        bcs[i] = make_pair(b, c);
    }

    sort(as.begin(), as.end());
    sort(bcs.begin(), bcs.end(), [](auto a, auto b) {return a.second > b.second;});

    int ptr = 0;
    for (int i = 0; i < m; i++) {
        while(bcs[i].first > 0 && as[ptr] < bcs[i].second && ptr < n) {
            as[ptr] = bcs[i].second;
            bcs[i].first--;
            ptr++;
        }
    }

    long long int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += as[i];
    }

    cout << sum << endl;
}


Measured memory_bytes: 1536
#include <iostream>
using namespace std;
int n,A,B,C,s[8],ans=1e9+7;;
void dfs(int n,int a,int b,int c,int ch){
    if(n==0){
        if(min(a,min(b,c))>0)ans=min(ans,abs(A-a)+abs(B-b)+abs(C-c)+10*ch);
        return ; 
    }
    dfs(n-1,a,b,c,ch);
    if(a>0)ch++;
    dfs(n-1,a+s[n-1],b,c,ch);
    if(a>0)ch--;
    if(b>0)ch++;
    dfs(n-1,a,b+s[n-1],c,ch);
    if(b>0)ch--;
    if(c>0)ch++;
    dfs(n-1,a,b,c+s[n-1],ch);
    if(c>0)ch--;
    return ;
}
int main(void){
    cin>>n>>A>>B>>C;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    dfs(n,0,0,0,0);
    cout<<ans<<endl;
}


Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define ushi int
#define tapu main
#define nichia (
#define kunn void
#define wara )

using ll = long long;

const int INF = 1073741823;
const int MINF = -1073741823;
const ll LINF = ll(4661686018427387903);
const ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/

int main(){

	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n), c(n);
	rep(i, n)scanf("%d", &a[i]);
	rep(i, n)scanf("%d", &b[i]);
	rep(i, n)scanf("%d", &c[i]);

	sort(all(a));
	sort(all(c));
	ll ans = 0;
	for (auto aa : b) {
		auto ite1 = lower_bound(all(a), aa);
		auto ite2 = upper_bound(all(c), aa);
		int dist1 = distance(a.begin(), ite1), dist2 = distance(ite2, c.end());
		ans += (ll)dist1 * dist2;
	}
	printf("%lld\n", ans);
	Please AC;
}


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

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, k;
    cin >> n >> k;
    vector<ll> to(n), vis(n+1, 0);
    for(ll& x: to)
        cin >> x, --x;
    ll id = 0;
    bool bl = 1;
    vis[0] = 1;
    for(ll i=1; i<=k; i++){
        id = to[id];
        if(vis[id]&&bl){
            k-=i;
            k%=(i+1-vis[id]);
            i = 0;
            bl = 0;
        }
        else
            vis[id]=i+1;
    }
    cout << id+1;
    return 0;
}


Measured memory_bytes: 6368
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=1e9+7,maxn=1e6+7;
ll dp[maxn];///dp[i]表示只从前i个中选择i/2个
ll sum[maxn];
ll a[maxn],n;
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        if(i>1) sum[i]=sum[i-2]+a[i];
        else sum[i]=a[i];
    }
    for(ll i=2;i<=n;i++)
        if(i%2) dp[i]=max(dp[i-2]+a[i],dp[i-1]);
        else dp[i]=max(dp[i-2]+a[i],sum[i-1]);
    cout<<dp[n];
    return 0;
}


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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

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

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

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

const int MX = 1000;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    V<int> A(N);
    rep(i, N) cin >> A[i];
    V<ll> dp(N + 1);
    dp[0] = 1000;
    rep(i, N) {
        if (i) chmax(dp[i], dp[i - 1]);
        for (int j = i + 1; j < N; ++j) {
            ll nx = dp[i] / A[i] * A[j] + dp[i] % A[i];
            chmax(dp[j], nx);
        }
    }
    debug(dp);
    cout << *max_element(ALL(dp)) << endl;

    return 0;
}

Measured memory_bytes: 3580