akhauriyash/Code-Regression huggingface dataset:
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}
// {{{ MaxFlow
class MaxFlow{
    private:
        // destination, capacity, reverse edge index
        const ll inf=1e18;
        struct edge { ll to, cap, rev; };
        ll _n;
        vector<vector<edge>> G;
        vector<bool> used;

        ll dfs (ll src, ll dst, ll flow){
            if (src==dst)
                return flow;
            used[src]=true;
            rep(i,0,G[src].size()){
                edge &e = G[src][i];
                if (!used[e.to] && e.cap > 0) {
                    ll d = dfs(e.to, dst, min(flow, e.cap));
                    if (d>0){
                        e.cap -= d;
                        G[e.to][e.rev].cap += d;
                        return d;
                    }
                }
            }
            return 0;
        }

    public:
        MaxFlow (ll numOfVertex){
            _n = numOfVertex;
            G = vector<vector<edge>>(_n);
        }

        // 0<=src,dst<numOfVertex
        void addEdge(ll src, ll dst, ll cap) {
            G[src].push_back(edge{dst, cap, (ll)G[dst].size()});
            G[dst].push_back(edge{src, 0, (ll)G[src].size()-1});
        }

        ll maxFlow(ll src, ll dst){
            ll flow = 0;
            while(true){
                used = vector<bool>(_n, false);
                ll f = dfs(src, dst, inf);
                if (f==0){
                    return flow;
                }
                flow += f;
            }
        }
};
// }}}

signed main() {
    // 0: start
    // 1~ : red
    // 1001 ~: blue
    // 2000: end
    MaxFlow mf(30000);
    ll N;
    cin>>N;
    vector<PLL> r(N),b(N);
    rep(i,0,N) { cin>>r[i].first>>r[i].second; mf.addEdge(0, i+1, 1); }
    rep(j,0,N) { cin>>b[j].first>>b[j].second; mf.addEdge(j+1001, 2000, 1); }
    rep(i,0,N) // red
        rep(j,0,N) // blue
            if (r[i].first < b[j].first && r[i].second < b[j].second)
                mf.addEdge(i+1, j+1001, 1);
    cout<<mf.maxFlow(0,2000)<<endl;
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;
}
using ll = long long;
const ll MOD = 1e9 + 7;
const long long INF = 1LL << 60;

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

    vector<int> f(100000, 0);

    for (int x = 1; x <= 100; x++)
    {
        for (int y = 1; y <= 100; y++)
        {
            for (int z = 1; z <= 100; z++)
            {

                f.at(x * x + y * y + z * z + x * y + y * z + z * x) += 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cout << f.at(i) << endl;
    }
}

Measured memory_bytes: 3776
import sys
import bisect
import math
import itertools


# \n
def input():
    return sys.stdin.readline().rstrip()


def dist(Z1, Z2):
    x1, y1 = Z1
    x2, y2 = Z2
    return (x1 - x2) ** 2 + (y1 - y2) ** 2


def middle(X1, X2, X3):
    x1, y1 = X1
    x2, y2 = X2
    x3, y3 = X3

    alpha = x1 - x2
    beta = y1 - y2
    gamma = x2 - x3
    delta = y2 - y3

    div = (alpha * delta - beta * gamma) * 2
    if div == 0:
        return 60000, 60000

    div = 1 / div
    upper = x1 ** 2 + y1 ** 2 - x2 ** 2 - y2 ** 2
    lower = x2 ** 2 + y2 ** 2 - x3 ** 2 - y3 ** 2

    a = div * (delta * upper - beta * lower)
    b = div * (-gamma * upper + alpha * lower)

    return a, b


def main():
    NN, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod

    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 5 + 10
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    sup = 0
    inf = 0

    for i in range(NN - K + 1):
        c = cmb(NN-i-1, K - 1, mod)

        inf += c*A[i]
        inf %=mod
        sup += c*A[-i-1]
        sup %=mod

    print((sup-inf)%mod )


if __name__ == "__main__":
    main()


Measured memory_bytes: 117644
#include<cstdio>
#include<vector>
using namespace std;

const int b[7] = {0,9,12,15,18,21,30};
inline bool check(const vector<int> &c){
  for(int x=0;x<6;x++){
    for(int i=b[x];i<b[x+1]-1;i++)if(c[i]!=c[i+1])return false;
  }
  return true;
}

inline void rot(vector<int> &c, int d){
  if(d == 0){
    swap(c[0],c[23]); swap(c[3],c[26]); swap(c[6],c[29]);
    swap(c[15],c[17]); swap(c[9],c[20]);
  }
  if(d == 1){
    swap(c[6],c[21]); swap(c[7],c[22]); swap(c[8],c[23]);
    swap(c[9],c[11]); swap(c[12],c[17]);
  }
  if(d == 2){
    swap(c[2],c[21]); swap(c[5],c[24]); swap(c[8],c[27]);
    swap(c[12],c[14]); swap(c[11],c[18]);
  }
  if(d == 3){
    swap(c[0],c[27]); swap(c[1],c[28]); swap(c[2],c[29]);
    swap(c[18],c[20]); swap(c[14],c[15]);
  }
}

int rec(int d, vector<int> &c){
  if(check(c))return d;
  if(d>=8)return 8;

  int res = 8;
  for(int i=0;i<4;i++){
    rot(c,i);
    res = min(res, rec(d+1,c));
    if(res==d)break;
    rot(c,i);
  }
  return res;
}

int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    vector<int> p(30);
    for(int i=0;i<30;i++)scanf("%d\n",&p[i]);
    printf("%d\n",rec(0,p));
  }
}

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

public class Main {
    static Scanner sc;
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        Arrays.sort(A);
        int ct = 0;
        for(int i = 0; i < N - 2; i++) {
            for(int j = i + 1; j < N - 1; j++) {
                int target = A[i] + A[j];
                int difference = N - 1 - j;
                int maxValidIndex;
                if(A[N - 1] < target) {
                    maxValidIndex = N - 1;
                } else {
                    //binary search maximum valid k
                    //0,...,i,...,j,j+1,...N-1
                    int offset = 0;
                    for(int b = difference; b >= 1; b /= 2) {
                        while(b+offset < difference &&A[b + offset + j] < target) {
                            offset += b;
                        }
                    }
                    maxValidIndex = j + offset;
                }
                ct += (maxValidIndex - j);
            }
        }

        System.out.println(ct);
    }
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int m;
  while (cin >> m, m) {
    int a[7], b[7];
    for (int i = 0; i < m; i++) {
      cin >> a[i] >> b[i];
    }
    int dp[8][1010] = {};
    dp[0][0] = 1;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j <= 1000; j++) {
        for (int k = 0; k <= b[i] && j - a[i] * k >= 0; k++) {
          dp[i + 1][j] += dp[i][j - a[i] * k];
        }
      }
    }
    int g;
    cin >> g;
    for (int i = 0; i < g; i++) {
      int n;
      cin >> n;
      cout << dp[m][n] << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3160
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
B = sorted(list(map(int, input().split())), reverse = True)
C = sorted(list(map(int, input().split())), reverse = True)

cakes = []
for i in range(0, min([K, X])):
  for j in range(0, min([K // (i + 1) + 1, Y])):
    for k in range(0, min([K // ((i + 1) * (j + 1)) + 1, Z])):
      cakes.append([i, j, k])
      
values = [A[cake[0]] + B[cake[1]] + C[cake[2]] for cake in cakes]
list.sort(values, reverse = True)

for i in range(K):
  print(values[i])

Measured memory_bytes: 23128
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k=int(input())
print(l[k-1])

Measured memory_bytes: 3316
/* include c++ libraries */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>

/* include c-lang libraries */
#include <climits>
#include <cmath>

/* include my libraries */
//#include <show_vec.hh>

using namespace std;

#define LINE DEBUG{ printf("LINE : %d\n", __LINE__); }
#define DEBUG if(false)

using ll = long long;
template<class T> using vec = vector<T>;

const int MOD = 1000000007;

int main(){
  int N;
  cin >> N;
  int count = 0;
  bool boolean = false;
  for(int i = 0; i < N; i++){
    int d1, d2;
    cin >> d1 >> d2;
    if(d1 == d2){
      count++;
      if(count == 3){
        boolean = true;
      }
    }else{
      count = 0;
    }
  }
  if(boolean){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;

  }

  return 0;
}


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

// #define multitest 1
// #define Debug 1
#ifdef Debug
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
{
	const char *comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
#else
#define db(...)
#endif

typedef long long ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
const long long mod = 1000000007;

const int nax = 1e5 + 10;
vector<int> Edges[nax];
int n, k;

int _n = 1e5 + 10;
vector<ll> Fact(_n), Inv(_n);
int kmod = 1000000007;

ll mul(ll a, ll b)
{
	return a * b % kmod;
}

ll power(int base, int index)
{
	if (index == 0)
		return 1;
	ll temp = power(base, index / 2);
	temp = mul(temp, temp);
	if (index & 1)
		temp = mul(temp, base);
	return temp;
}

void pre()
{
	Fact[0] = 1;
	for (int i = 1; i < _n; ++i)
		Fact[i] = mul(Fact[i - 1], i);
	Inv[_n - 1] = power(Fact[_n - 1], kmod - 2);
	for (int i = _n - 2; i >= 0; --i)
		Inv[i] = mul(Inv[i + 1], (1 + i));
}

ll ncr(int n, int r)
{
	if (n < 0 || r < 0 || n - r < 0)
		return 0;
	return mul(Fact[n], mul(Inv[0], Inv[n - r]));
}

ll solve(int node, int parent, int grand)
{
	ll ways = 1, k1;
	if (parent == 0)
	{
		k1 = k - 1;
	}
	else
	{
		k1 = k - 2;
	}
	if (Edges[node].size() == 0)
		return ways;
	if (parent)
		ways = mul(ways, ncr(k1, (Edges[node].size() - 1)));
	else
		ways = mul(ways, ncr(k1, (Edges[node].size())));
	for (auto child : Edges[node])
	{
		if (child == parent)
			continue;
		auto temp = solve(child, node, parent);
		ways = mul(ways, temp);
	}
	db(k1);
	db(node, ways, ncr(k1, (Edges[node].size() - 1)));
	return ways;
}

void solve()
{
	pre();
	int u, v;
	cin >> n >> k;
	for (int i = 0; i < n - 1; ++i)
	{
		cin >> u >> v;
		Edges[u].pb(v);
		Edges[v].pb(u);
	}
	cout << (k * solve(1, 0, 0)) % mod << '\n';
}

int main()
{
#ifndef Debug
	ios_base::sync_with_stdio(0);
	cin.tie(0);
#endif
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
	while (t--)
		solve();
	return 0;
}

Measured memory_bytes: 12032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll A,B,X;
  cin>>A>>B>>X;
  if(X>A+B)cout<<"NO"<<endl;
  else if(X<A) cout<<"NO"<<endl;
  else cout<<"YES"<<endl;
}


Measured memory_bytes: 256
# include<iostream>
using namespace std;
const  int MAXN = 2e5+5;
int A[MAXN];
int B[MAXN];
int C[MAXN];
int main ()
{
	 long long N,K;
	 cin>>N>>K;

	 for(int i=1;i<=N;i++)
	 {
	 	 cin>>A[i];
	 }
	 

	 long long id=1;
	 long long t=0;
      C[t++]=1;
     while(B[id]==0)
     {
     	  B[id]=1;
     	  id = A[id];
          C[t++]=id;	 
	 }
	 
	 long long begin;
	 for(int i=0;i<t;i++)
	 {
	 	   if(C[i]==id)
	 	   {
	 	   	   begin = i;
	 	   	   break;
			}
	 }
	 
	

	 begin++;
	 if(K<=begin)
     {
     	  cout<<C[K]<<endl;
	 }
	 else
	 {
	 	   cout<<C[(K-begin)%(t-begin)+begin]<<endl; 
		  }	 
	 
	  
	  
	
	
}

Measured memory_bytes: 5828
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define INF 1e+9


int main() {
	int n, m;
	cin >> n >> m;
	int a;
	for (int i = 0; i < m; i++) {
		cin >> a;
		n -= a;
	}
	if (n < 0)cout << -1 << endl;
	else cout << n << endl;



	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    int n, m, k;
    while (cin >> n >> m >> k) {
        vector<int> friends(n + 1, 0);
        vector<vector<int>> connect(n + 1, vector<int>());
        vector<int> candidate(n + 1, 0);
        vector<int> dsu(n + 1);
        vector<bool> visit(n + 1, 0);
        vector<pair<int, int>> block;
        for (int i = 1; i <= n; i++) {
            dsu[i] = 1;
        }
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            connect[a].push_back(b);
            connect[b].push_back(a);
            friends[a]++;
            friends[b]++;
        }
        for (int i = 0; i < k; i++) {
            int c, d;
            cin >> c >> d;
            block.push_back({c, d});
        }
        for(int i = 1; i <= n; i++){
            if(!visit[i]){
                queue<int> bfs;
                bfs.push(i);
                visit[i]=true;
                int cnt = 0;
                while(!bfs.empty()){
                    int cur = bfs.front();
                    cnt++;
                    dsu[cur]=i;
                    bfs.pop();
                    for(auto j:connect[cur]){
                        if(!visit[j]){
                            bfs.push(j);
                            visit[j]=true;
                        }
                    }
                }
                candidate[i]=cnt;
            }
            candidate[i]=candidate[dsu[i]];
        }
        for(int i = 1; i <= n; i++){
            candidate[i]-=(friends[i]+1);
        }
        for(int i = 0; i < k; i++){
            if(dsu[block[i].first]==dsu[block[i].second]){
                candidate[block[i].first]--;
                candidate[block[i].second]--;
            }
        }
        for(int i = 1; i <= n; i++){
            if(i != 1)cout<<' ';
            cout<<candidate[i];
        }
        cout<<'\n';
    }
}

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

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

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

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

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

    cin>>n>>h>>w;
    Cout((n-h+1)*(n-w+1));
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

n = int(input())

d = defaultdict(int)

for i in range(1, 120):
    for j in range(1, 120):
        for k in range(1, 120):
            num = i**2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            d[num] += 1

for i in range(1,n+1):
    print(d[i])


Measured memory_bytes: 14400
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int a,s,d;
	cin>>a>>s>>d;
	cout<<a+s+d+10*max(a,max(s,d))-max(a,max(s,d));
    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int n, k, r, s, p;
    cin >> n >> k >> r >> s >> p;

    string t;
    cin >> t;

    int ans = 0;

    int use[n] = {};

    rep(i,n){
        if(i < k){
            if(t[i] == 's') ans += r;
            if(t[i] == 'p') ans += s;
            if(t[i] == 'r') ans += p;
        }else{
            if(t[i] != t[i-k]){
                if(t[i] == 's') ans += r;
                if(t[i] == 'p') ans += s;
                if(t[i] == 'r') ans += p;
            }else{
                if(use[i - k] == 0){
                    use[i] = -1;
                }else{
                    if(t[i] == 's') ans += r;
                    if(t[i] == 'p') ans += s;
                    if(t[i] == 'r') ans += p;
                }
            }
        }
    }

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


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define R register
#define ll long long
#define mp make_pair
#define pii pair<int, int>
using namespace std;

ll n, ans;

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int main() {
    read(n);
    ans = n - 1;
    for (R int i = 1, sr = sqrt(n); i <= sr; ++i)
        if (n % i == 0)
            ans = min(ans, i + n / i - 2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int n,q,C=0,i,j,L,M,R;
  int S[100000],T[50000];

  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&S[i]);
  }

  scanf("%d",&q);
  for(i=0; i<q; i++){
    scanf("%d",&T[i]);
    L = 0;
    R = n;
    while(L<R){
      M = (L+R)/2;
      if(S[M]==T[i]){
        C++;
        break;
      }
      if(S[M]<T[i])
        L = M+1;
      else if(S[M]>T[i])
        R = M;
    }
  }
  printf("%d\n",C);

  return 0;
}


Measured memory_bytes: 2380
S = input()
l = len(S)
toal = 0
for i in range(1 << (l-1)):
    a = int(S[0])
    sum_t = 0
    for j in range(l-1):
        if ((i >> j) & 1):
            sum_t += a
            a = 0
        a *= 10
        a += int(S[j+1])
    sum_t += a 
    toal += sum_t
    
print(toal)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,ans;
  cin >> n >> m;
  if(m>n){
    vector<int> pos(m);
    for(int i=0; i<m;i++)
      cin >> pos.at(i);
    sort(pos.begin(),pos.end());
    vector<int> dis(m-1);
    for(int i=0;i<m-1;i++)
      dis.at(i)=pos.at(i+1)-pos.at(i);
    sort(dis.begin(),dis.end());
    ans=0;
    for(int i=0;i<n-1;i++)
      ans+=dis.at(m-2-i);
    ans=pos.at(m-1)-pos.at(0)-ans;
    cout << ans << endl;
  }
  else
    cout << '0' << endl;
}

Measured memory_bytes: 1024
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

def factrial(n):
    a = 0
    for i in range(1, n+1):
        a += i
    return a

nf = 0 if n < 2 else int(factrial(n - 1))
mf = 0 if m < 2 else int(factrial(m - 1))

print(nf + mf)


Measured memory_bytes: 2940
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	void run(){
		for(;;){
			int n = sc.nextInt();
			int r = sc.nextInt();
			
			if((n|r) ==0) {
				break;
			}
			
			
			int[] z = new int[n];
			for(int i = 0; i < n ; i++){
				z[i] = n - i;
			}
			
			for(int i = 0; i < r ; i++){
				int p = sc.nextInt() - 1;
				int c = sc.nextInt();
				
				int[] z2 = z.clone();
				
				for(int j = 0 ; j < c ; j++){
					z2[j] = z[j+p];
				}
				for(int j = 0; j < p ; j ++){
					z2[j+c] = z[j];
				}
				z = z2;
//				System.out.println(Arrays.toString(z));
			}
			System.out.println(z[0]);
		}
		
	}
	public static void main(String[] args){
		Main m = new Main();
		m.run();
	}
}

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

int main()
{
    vector<int> v;
    int n;
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }
    int i;
    if (prev_permutation(v.begin(), v.end()))
        for (i = 0; i < v.size(); i++)
        {
            cout << v[i] << " \n"[i == v.size() - 1];
        }

    next_permutation(v.begin(), v.end());
    for (i = 0; i < v.size(); i++)
    {
        cout << v[i] << " \n"[i == v.size() - 1];
    }

    if (next_permutation(v.begin(), v.end()))
        for (i = 0; i < v.size(); i++)
        {
            cout << v[i] << " \n"[i == v.size() - 1];
        }
    return 0;
}


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

int rnd(double t){
	if(t>=0.0){
		return (int)(t+0.5);
	}else{
		return (int)(t-0.5);
	}
}
void prnt(double t){
	if(t<0.0){
		cout<<"-";
		t*=-1;
	}
	cout<<(int)t<<"."<<(int)(t*10)-(int)t*10<<(int)(t*100)-(int)(t*10)*10<<(int)(t*1000)-(int)(t*100)*10;
}
int main(){
	double a,b,c,d,e,f,x,y;
	while(cin>>a>>b>>c>>d>>e>>f){
		x=(c*e-b*f)/(a*e-b*d);
		y=(a*f-c*d)/(a*e-b*d);
		x=rnd(x*1000.0)/1000.0;
		y=rnd(y*1000.0)/1000.0;
		prnt(x);
		cout<<" ";
		prnt(y);
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main () {
    string s[3];
    cin >> s[0] >> s[1] >> s[2];

    for (int i = 0; i < 3; i++) {
        transform(s[i].cbegin(), s[i].cend(), s[i].begin(), ::toupper);
        cout << s[i][0];
    }
    cout << endl;
}


Measured memory_bytes: 256
n = gets.to_i
list = ("a".."z").to_a.map{|chr|[chr,50]}
n.times do
  s = gets.chomp.chars
  list.each do |chr|
    if s.count(chr[0]) < chr[1]
      chr[1] = s.count(chr[0])
    end
  end
end
ans = ""
list.each do |chr|
  ans += chr[0] * chr[1]
end
puts ans
  

Measured memory_bytes: 14304
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
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;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ


signed main(){
    int n,k; cin >> n >> k;
    if(k==1) cout << 0 << endl;
    else cout << n-k << endl;
}


Measured memory_bytes: 3636
N, K = map(int, input().split())

if K % 2:
    print((N // K) ** 3)

else:
    x = 0
    y = 0
    
    # Kで割った時、余りが0になる数字の個数
    for i in range(K, N+1):
        if not i % K:
            x += 1

    # Kで割った時、余りがK/2になる数字の個数
    for i in range(1, N+1):
        if i % K == K / 2:
            y += 1

    print(x ** 3 + y ** 3)

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

void insertionSort(vector<int> A, int N) {
    REP(i, N) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = v;
        rep(i, N - 1) cout << A[i] << " ";
        cout << A[N - 1] << endl;
    }
    return;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    
    rep(i, N - 1) cout << A[i] << " ";
    cout << A[N - 1] << endl;
    insertionSort(A, N);
}



Measured memory_bytes: 3164
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<functional>
#include<vector>
#include<queue>
using namespace std;
#define f(i,n) for(int i=0;i<(int)n;i++)
#define MOD 1000000009

int main(void){
	char a[100000];
	f(i, 100000)a[i] = 0;
	int k;
	int n;
	int x, y, z;
	int ans = 0;
	bool m = true;

	scanf("%s", a);
	n = strlen(a);
	x = 0;
	y = 0;
	z = 0;
	k = n / 3;
	f(i, n){
		if (a[i] == 'a')x++;
		if (a[i] == 'b')y++;
		if (a[i] == 'c')z++;
	}
	if (x < k||k + 1 < x)m = false;
	if (y < k||k + 1 < y)m = false;
	if (z < k||k + 1 < z)m = false;

	if (m)printf("YES\n");
	else printf("NO\n");

	return 0;
}

Measured memory_bytes: 256
type StrL = (String,Int)
cmp (s1,l1) (s2,l2)
  | l1<l2 = LT
  | l1>l2 = GT
  | otherwise = compare s1 s2

is753 = (==(True,True,True)) . foldl f (False,False,False) where
  f (b7,b5,b3) '7' = (True,b5,b3)
  f (b7,b5,b3) '5' = (b7,True,b3)
  f (b7,b5,b3) '3' = (b7,b5,True)

b2i True = 1
b2i False = 0

solv n = go n ("",0) where
  go n a@(sa,la)
    | a `cmp` n == GT = 0
    | otherwise = 
        b2i (is753 sa) + go n ('7':sa,la+1)+ go n ('5':sa,la+1)+ go n ('3':sa,la+1)

main = do
  n <- getLine
  print $ solv (n, length n)


Measured memory_bytes: 892
import heapq

N,K = map(int,input().split())

V = list(map(int,input().split()))

ans = 0

for R in range(N-1):

    R += 1

    for L in range(R):

        if (L + 1) + (N - R) > K:
            continue

        q = []
        vsum = 0
        for i in range(N):

            if i <= L or R <= i:
                heapq.heappush(q,V[i])
                vsum += V[i]

        for i in range(K - (L + 1) - (N - R)):

            if len(q) > 0 and q[0] < 0:
                now = heapq.heappop(q)
                vsum -= now

            else:
                break

        ans = max(ans,vsum)

for L in range(N):

    if L+1 > K:
        continue

    q = []
    vsum = 0

    for i in range(N):
        if i <= L:
            heapq.heappush(q,V[i])
            vsum += V[i]

    for i in range(K - (L+1)):
        if len(q) > 0 and q[0] < 0:
            now = heapq.heappop(q)
            vsum -= now
        else:
            break
    ans = max(ans,vsum)

for R in range(N):

    if N-R > K:
        continue

    q = []
    vsum = 0

    for i in range(N):
        if R <= i:
            heapq.heappush(q,V[i])
            vsum += V[i]

    for i in range(K - (L+1)):
        if len(q) > 0 and q[0] < 0:
            now = heapq.heappop(q)
            vsum -= now
        else:
            break
    ans = max(ans,vsum)

print (ans)


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

using namespace std;

#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'

constexpr int INF = ((int64_t)2e18);
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 3;

vector<int> adj[MAXN];

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;

  // cin >> t;
  t = 1;

  while (t--) {
    int n;
    cin >> n;

    int m;
    cin >> m;

    vector<int> arr(n + 1);
    for (int i = 1; i <= n; ++i)
      cin >> arr[i];

    while (m--) {
      int u, v;
      cin >> u >> v;

      adj[u].eb(v);
      adj[v].eb(u);
    }

    int ans = 0;

    for (int i = 1; i <= n; ++i) {
      bool ok = true;
      for (int v : adj[i])
        if (arr[i] <= arr[v])
          ok = false;
      ans += ok;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 12172
import numpy as np
n,d=map(int,input().split())
D=[]
for i in range(n):
    List=list(map(int,input().split()))
    D.append(List)
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        cou=0
        for k in range(d):
            # print(i,j,k)
            cou+=(D[i][k]-D[j][k])**2
            
        if(np.sqrt(cou)%1.0==0):
            ans+=1
print(ans)

Measured memory_bytes: 21744
N=int(input())
l=[]
for i in range(N):
  l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[2],reverse=True)
x=l[0][0]
y=l[0][1]
h=l[0][2]

for j in range(101):
  for k in range(101):
    height_summit = h+abs(x-j)+abs(y-k)
    flag=1
    for point in l:
      if point[2] == max(height_summit-abs(point[0]-j)-abs(point[1]-k), 0):
        pass
      else:
        flag=0
        break
    if flag:
      print(j,k,height_summit)
      quit()

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

int main() {
  int a,b; cin >> a >> b;
  if (a>2*b) {
  cout << a-2*b << endl;
  }
  else cout << 0 << endl;
}

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

ll gcd(ll x, ll y);
int fac(ll n, vector<int> num);

const int INF = 1001001001;

//mint�p�̒萔 (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    ll a, b, x;
    cin >> a >> b >> x;
    

    ll b_x = b / x;
    if (0 / x == 0) {
        b_x++;
    }

    ll a_x = (a == 0)? 0: (a - 1) / x;
    if (a != 0 && 0 / x == 0) {
        a_x++;
    }


    ll ans = b_x - a_x;
    
    cout << ans << endl;

    return 0;
}

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
ll gcd(ll x, ll y) {
    ll num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

/*�f��������*/
//���색�C�u����
int fac(ll n, vector<int> num) {
    ll kazu = n;
    for (int i = 2; i <= sqrt(n); i++) {
        while (1) {
            if (kazu % i != 0) break;

            kazu /= i;
            num[i]++;
        }
    }
    if (kazu == n && n != 1) return 1;
    int ans = 0;
    if (kazu != 1) ans++;
    for (int i = 2; i <= sqrt(n); i++) {
        for (int j = 1; j <= num[i]; j++) {
            num[i] -= j;
            ans++;
        }
    }
    return ans;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;

struct mint {
  ll x;
  mint(ll x = 0): x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
  mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
  int k;
  string s;
  cin >> k >> s;
  int ss = s.size();
  combination nCr(ss + k);
  mint ans = 0;
  for (int i = ss; i <= k + ss; i++) {
    mint res = nCr(i - 1, ss - 1);
    res *= mint(25).pow(i - ss);
    res *= mint(26).pow(k + ss - i);
    ans += res;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 35596
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
#define MOD (LL)(1e9+7)

int main(){
	int N;
	cin >> N;
	double v[50];
	for(int i=0; i<N; i++) cin >> v[i];
	sort(v, v+N);
	double ans = v[0];
	for(int i=1; i<N; i++){
		ans = (ans+v[i])/2;
	}
	cout << setprecision(18) << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int s, ans;
  cin >> s;
  for (int i=0;;i++){
    if(s==4||s==2||s==1){
      ans=i+1;
      break;
    }
    if(s%2==0){
      s/=2;
    }
    else {
      s=s*3+1;
    }
  }
  cout << ans+3 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int A, B;
  cin >> A >> B;
  if(A != 1 && B != 1){
cout << 1 << endl;
  }else if(A != 2 && B != 2){
cout << 2 << endl;
  }else{
cout << 3 << endl;
  }
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	 int n;
	cin>>n;
	int i, count=0;
	for(i=1; i<=n; i+=2)
	count++;
	double x=(double)count/(double)n;
	cout<<fixed<<setprecision(10)<<x<<endl;
	}

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

int main() {
  // ここにプログラムを追記
  int N;
  cin >> N;
  int a,b,c;
  a=N/100;
  b=N%100/10;
  c=N%100%10;
  cout<<a+b+c<<endl;
  return 0;
}

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

bool is_square(int n)
{
    for (int i = 0; i <= n; i++)
    {
        if (i * i == n)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    string o, e;
    cin >> o >> e;
    string ans;
    ans.resize(o.length() + e.length());
    for (size_t i = 0; i < o.length(); i++)
    {
        ans[2 * i] = o[i];
    }
    for (size_t i = 0; i < e.length(); i++)
    {
        ans[2 * i + 1] = e[i];
    }
    cout << ans << endl;

    return 0;
}

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

#define NIL NULL

struct node{
  int key;
  struct node *right;
  struct node *left;
  struct node *parent;
};
typedef struct node * Node;

Node g_root;

void insert(int k);
void inorder(Node u);
void preorder(Node u);
Node treeSearch(Node x, int k);

int main(){
  int n,i,x;
  char com[20];

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    scanf("%s",com);
    if(com[0] == 'f'){
      scanf("%d",&x);
      Node t = treeSearch(g_root, x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }else if(com[0] == 'i'){
      scanf("%d",&x);
      insert(x);
    }else if(com[0] == 'p'){
      inorder(g_root);
      printf("\n");
      preorder(g_root);
      printf("\n");
    }
  }
  
  return 0;
}

void insert(int k){
  Node y = NIL;
  Node x = g_root;
  Node z;

  z = (Node)malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }

  z->parent = y;
  if(y == NIL) g_root = z;
  else if(z->key < y->key){
    y->left = z;
  }else{
    y->right = z;
  }
}

void inorder(Node u){
  if(u == NIL) return;

  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u == NIL) return;

  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

Node treeSearch(Node x, int k){
  while(x != NIL && k != x->key){
    if(k < x->key) x = x->left;
    else x = x->right;
  }
  return x;
}



Measured memory_bytes: 20552
import java.util.HashSet;
import java.util.Scanner;

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

        int N = scanner.nextInt();
        int sqrtN = (int) Math.floor(Math.sqrt(N));
        int[] cnt = new int[N];


        for (int x = 1; x < sqrtN; x++) {
            for (int y = 1; y < sqrtN; y++) {
                for (int z = 1; z < sqrtN; z++) {
                    int n = x * x +
                            y * y +
                            z * z +
                            x * y +
                            y * z +
                            z * x;

                    if (n > cnt.length) continue;
                    cnt[n - 1]++;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.println(cnt[i]);
        }
    }
}


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

int main(){
	while(1){
		int n, m;
		char a[1000][3];	
		
		scanf(" %d", &n);
		if(n==0) break;
		for(int i=0; i<n; ++i){
			scanf(" %c %c", &a[i][0], &a[i][1]);	
		}
		
		scanf(" %d", &m);
		for(int i=0; i<m; ++i){
			char c;	
			scanf(" %c", &c);
			
			for(int j=0; j<n; ++j){
				if(c==a[j][0]){
					c=a[j][1];	
					break;
				}
			}
			
			printf("%c", c);
		}
		
		printf("\n");
	}
	return 0;
}

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

int main() 
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
  ll n,m,p;cin>>n>>m>>p;
  ll q=(p/n),w=(p/m);
  if((p%n)!=0)q++;
  if((p%m)!=0)w++;
  cout<<min(q,w);
 return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
     
    int main(void)
    {
     int r, g, b;
     
     scanf("%d", &r);
     scanf("%d", &g);
     scanf("%d", &b);
     
     int c = ((r * 100) + (g * 10) + b);
     if (c % 4) puts("NO");
     else puts("YES");
     
     
     return 0;
     
    }

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
  
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
  
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
  
bool visit[11][11][51][11][11];

struct state {
    int x, y, l, r;
    int cost, oxy;
    state(int x, int y, int l, int r, int c, int o):x(x),y(y),l(l),r(r),cost(c),oxy(o){}
    bool operator<(const state &r) const {
        return cost > r.cost; 
    }
};

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

int main(){
    int w, h;
    while(cin >> w >> h, w|h){
        int f, m, o;
        cin >> f >> m >> o;
        vector<vector<int> > c(h, vector<int>(w));
        rep(i, h) rep(j, w) cin >> c[i][j];
        
        memset(visit, 0, sizeof(visit));

        priority_queue<state> q;
        rep(i, w){
            state s(i, 0, i, i, 0, o-1);
            if(s.oxy <= 0) continue;
            s.cost = max(-c[0][i], 0);
            s.oxy = max(c[0][i] + s.oxy, s.oxy);
            if(s.oxy > m) s.oxy = m;
            q.push(s);
        }
        int ans = -1;
        while(!q.empty()){
            state s = q.top();
            q.pop();

            if(s.cost > f) continue;
            if(s.oxy <= 0) continue;

            if(visit[s.x][s.y][s.oxy][s.l][s.r]) continue;
            visit[s.x][s.y][s.oxy][s.l][s.r] = 1;
            
            if(s.y == h-1){
                ans = s.cost;
                break;
            }
            if(s.oxy <= 1) continue;

            rep(i, 3){
                int x = s.x+dx[i];
                int y = s.y+dy[i];

                if(x < 0 || x >= w || y < 0 || y >= h) continue;
                
                state next = s;
                next.x = x;
                next.y = y;
                next.oxy--;
                if(s.y != next.y) {
                    next.r = -1;
                    next.l = 11;
                }
                if(x < next.l || x > next.r){
                    next.r = max(next.r, x);
                    next.l = min(next.l, x);
                    if(c[y][x] > 0){
                        next.oxy = min(next.oxy+c[y][x], m);
                    }else{
                        next.cost -= c[y][x];
                    }
                }
                q.push(next);
            }
        }
        if(ans != -1) cout << ans << endl;
        else cout << "NA" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 2172
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]  # 違和感
G = [list(map(lambda x: int(x) - 1, input().split())) for i in range(N)]


# mod3でグループ分け
group = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        group[(i + j) % 3].append(G[i][j])


# 各グループについて色cに変更する際にかかるコスト
cost = [[0] * C for i in range(3)]
for c in range(C):
    for i, g in enumerate(group):
        tmp_cost = sum([D[gi][c] for gi in g if gi != c])
        cost[i][c] = tmp_cost


# 色のあてはめ方を全探索
ans = float('inf')
for c0, c1, c2 in permutations(range(C), r=3):
    tmp_ans = cost[0][c0] + cost[1][c1] + cost[2][c2]
    ans = min(ans, tmp_ans)

print(ans)


Measured memory_bytes: 8336
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second

int dp[200000];

signed main(){
  int n;
  cin>>n;
  vector<P>v(n);
  vector<int>V;
  r(i,n){
    int a,b;
    cin>>a>>b;
    v[i]=P(a,b);
    V.push_back(a);
    V.push_back(b);
  }
  sort(V.begin(),V.end());
  map<int,int>M;
  int c=0;
  r(i,V.size()){
    while(i!=V.size()-1&&V[i]==V[i+1])i++;
    M[V[i]]=c++;
  }
  r(i,n){
    int A=M[v[i].fi];
    int B=M[v[i].se];
    dp[A]++;
    dp[B+1]--;
  }
  int sum=0,ans=0;
  r(i,110000){
    ans=max(ans,dp[i]);
    dp[i+1]+=dp[i];
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 20008
# D - Checker

N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

print(ans)

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

int main(){
    long long N, ans = 0;;
    cin >> N;
    vector<string> S(N+1);
    unordered_map<string,long long> UM;
    for(int i = 1; i <= N; ++i) cin >> S[i];
    for(int i = 1; i <= N; ++i){
        sort(S[i].begin(), S[i].end());
        ++UM[S[i]];
    }
    for(auto itr = UM.begin(); itr != UM.end(); ++itr){
        ans += itr->second * (itr->second - 1.) / 2.;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13432
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T>
vector<T> dijkstra(Int s,vector<vector<pair<Int, T> > > & G,T INF){
  using P = pair<T, Int>;
  Int n=G.size();
  vector<T> d(n,INF);
  vector<Int> b(n,-1);
  priority_queue<P,vector<P>,greater<P> > q;
  d[s]=0;
  q.emplace(d[s],s);
  while(!q.empty()){
    P p=q.top();q.pop();
    Int v=p.second;
    if(d[v]<p.first) continue;
    for(auto& e:G[v]){
      Int u=e.first;
      T c=e.second;
      if(d[u]>d[v]+c){
	d[u]=d[v]+c;
	b[u]=v;
	q.emplace(d[u],u);
      }
    }
  }
  return d;
}

//INSERT ABOVE HERE
signed main(){
  Int n,m,s,t;
  cin>>n>>m>>s>>t;
  s--;t--;
  using P = pair<Int, Int>;
  vector<vector<P> > G(n);
  
  for(Int i=0;i<m;i++){
    Int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;c--;
    G[a].emplace_back(b,d);
    G[a].emplace_back(c,d);
    G[b].emplace_back(a,d);
    G[b].emplace_back(c,d);
    G[c].emplace_back(a,d);
    G[c].emplace_back(b,d);
  }

  const Int INF = 1e15;
  auto D=dijkstra(s,G,INF);

  cout<<D[t]<<endl;
  return 0;
}



Measured memory_bytes: 24212
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <algorithm>

#define MOD_BIG 1000000007
#define MOD_BIG2 998244353
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;
using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using std::vector;

#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

//////////////////////////////////////



//////////////////////////////////////

int main() {
    
    int N;
    cin >> N;
    int val = ceil(N * 100.0 / 108);
    int n = val * 1.08;
    if (n != N) {
        cout << ":(" << endl;
    } else {
        cout << val << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
if set(a) == {0}:
    print('Yes')
    exit()

flag = 0
if n % 3 == 0:
    if len(cnt) == 2:
        if cnt.get(0) == n // 3:flag = 1
    elif len(cnt) == 3:
        if len(set(cnt.values())) == 1:
            new_a = list(cnt.keys())
            if new_a[0]^new_a[1] == new_a[2]:flag = 1

print('Yes' if flag else 'No')

Measured memory_bytes: 20972