akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
a = list(int(input()) for _ in range(m))

MOD = 10**9 + 7
is_broken = [0] * (n+1)
dp = [0] * (n+1)
dp[0] = 1

for x in a:
    is_broken[x] = 1

for i in range(n):
    for j in range(i+1, min(n, i+2) + 1):
        if not is_broken[j]:
            dp[j] += dp[i]
            dp[j] %= MOD

print(dp[n])


Measured memory_bytes: 14380
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int D,C[26],S[365][26],T[365],Tans[365],V[365],Vorigin[365];
int last[365][26],last_sim[365][26],last2[26];
int vmax;
int steps=0;

void greedy(){
    int dadd,i,j,k,l,i_calc,tbest,score,vbest;
    for(dadd=0;dadd<=26;++dadd){
        //リセット
        for(i=0;i<D;i++){
            if(i<26)last2[i]=0;
            for(j=0;j<26;j++){
                last[i][j]=0;
            }
        }

        for(i=0;i<D;i++){
            i_calc=min(i+dadd+1,D);
            //cout<<i_calc<<endl;
            for(j=0;j<26;j++){
                //得点の初期化
                //cout<<i<<endl;
                if(i==0){
                    V[i]=0;
                }else{
                    V[i]=V[i-1];
                }
                //lastの初期化
                if(i==0)for(k=0;k<26;k++)last[i][k]=0;
                else for(k=0;k<26;k++)last[i][k]=last[i-1][k];

                last[i][j]=i;
                V[i]+=S[i][j];

                for(k=0;k<26;k++)
                    for(l=i;l<i_calc;l++)V[i]-=C[k]*(l-last[i][k]);

                if(j==0||V[i]>=vmax){
                    vmax=V[i];
                    tbest=j;
                }
            }
            if(i==0)for(j=0;j<26;j++)last[i][j]=0;
            else for(j=0;j<26;j++)last[i][j]=last[i-1][j];
            T[i]=tbest;
            last[i][tbest]=i;
        }

        //得点の再計算
        score=0;
        for(i=0;i<26;i++)last2[i]=0;
        for(i=0;i<D;i++){
            score+=S[i][T[i]];
            last2[T[i]]=i;
            for(j=0;j<26;j++)score-=C[j]*(i-last2[j]);
        }

        if(dadd==0||score>vbest){
            vbest=score;
            for(i=0;i<D;i++){
                if(i<26)Tans[i]=T[i];
                for(j=0;j<26;j++)last_sim[i][j]=last[i][j];
            }
        }
    }

    vmax=vbest;
    for(i=0;i<D;i++){
        if(i<26)T[i]=Tans[i];
        for(j=0;j<26;j++)last[i][j]=last_sim[i][j];
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int i,j;
    cin>>D;
    for(i=0;i<26;i++)cin>>C[i];
    for(i=0;i<D;i++)for(j=0;j<26;j++)cin>>S[i][j];
    greedy();

    for(i=0;i<D;i++)cout<<T[i]+1<<"\n";
    return 0;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w,a,b; cin >> h >> w >> a >> b;
    REP(i,h) {
        REP(j,w) {
            int x = (i<b)^(j<a);
            cout << x;
        }
        cout << '\n';
    }
    return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int main()
{
	
	int X, Y;
	int money = 0;

	cin >> X;
	if (X <= 3) {
		money += (4 - X) * 100000;
	}

	cin >> Y;
	if (Y <= 3) {
		money += (4 - Y) * 100000;

		if (Y == 1 && X == 1) {
			money += 400000;
		}
	}

	cout << money << endl;

	return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
const int INF = (int)1e9 + 1;

int a, b, n;
int dp[20][20];
bool kouji[20][20];

int main(void) {
	while (1) {
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++) {
				dp[i][j] = 0;
				kouji[i][j] = false;
			}
		}

		cin >> a >> b;
		if (a == 0 && b == 0) return 0;
		cin >> n;

		for (int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			x--; y--;
			kouji[x][y] = true;
		}

		dp[0][0] = 1;
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				if (kouji[i][j]) continue;

				if (0 <= i - 1 && i - 1 < a) {
					dp[i][j] += dp[i - 1][j];
				}

				if (0 <= j - 1 && j - 1 < b) {
					dp[i][j] += dp[i][j - 1];
				}
			}
		}

		cout << dp[a - 1][b - 1] << endl;
	}
}


Measured memory_bytes: 2988
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<double>heads,tails;
double dp[3005][3005];
bool vis[3005][3005];
double solve(int idx, int trials) {
	if (idx == heads.size()) { return 1.0; }
	if (vis[idx][trials]) { return dp[idx][trials]; }
	else {
		vis[idx][trials] = true;
		if (trials > 0) {
			double cond1= heads[idx] * solve(idx + 1, trials) + tails[idx] * solve(idx + 1, trials - 1);
			return dp[idx][trials] = cond1;
		}
		else {
			double cond2= heads[idx] * solve(idx + 1, trials);
			return dp[idx][trials] = cond2;
		}
	}
}


int main() {
	ll n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		double e;
		cin >> e;
		heads.push_back(e);
		tails.push_back(1.0 - e);
		
	}
	memset(dp, -1.0, sizeof(dp));
	cout <<fixed<<setprecision(10)<<solve(0, n / 2) << "\n";
	
	return 0;
}

Measured memory_bytes: 80000
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+4;
vector<int> adj[N];
vector<int> ve;
int deg[N];
int par[N];
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n,m; cin>>n>>m;
	for(int i=0; i<n+m-1; i++) {
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		deg[v]++;
	}
	for(int i=1; i<=n; i++) {
		if(!deg[i]) ve.push_back(i);
	}

	//for(int lol:v) cout<<lol<<" ";
	while(!ve.empty()) {
		int u=ve.back();
		//	cout<<u<<endl;
		ve.pop_back();
		for(int v:adj[u]) {
			deg[v]--;
			if(!deg[v]) {
				ve.push_back(v);
				par[v]=u;
			}
		}
	}
	for(int i=1; i<=n; i++) cout<<par[i]<<endl;
	return 0;
}


Measured memory_bytes: 8960
import sys

def count(n, b):
    res = 0
    while n:
        res += n % b
        n //= b
    return res

n = int(sys.stdin.readline().rstrip())

def main():
    res = float('inf')
    for i in range(n + 1):
        res = min(res, count(i, 6) + count(n - i, 9))
    print(res)

if __name__ ==  '__main__':
    main()

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

int id = INT_MAX;
int merge(int l, int r) {
	return min(l, r);
}

struct node {
	int val;
	int all;
	node *lch, *rch;
	int size;
	node(int v) : val(v), all(v), size(1) {
		lch = rch = nullptr;
	}
};

random_device rd;

int count(node *t) { return t == nullptr ? 0 : t->size; }
int que(node *t) { return t == nullptr ? id : t->all; }
node *update(node *t) {
	t->size = count(t->lch) + count(t->rch) + 1;
	t->all = merge(que(t->lch), merge(t->val, que(t->rch)));
	return t;
}
node *merge(node *l, node *r) {
	if (l == nullptr || r == nullptr) return l == nullptr ? r : l;
	if (rd() % (l->size + r->size) < (unsigned)l->size) {
		l->rch = merge(l->rch, r);
		return update(l);
	}
	else {
		r->lch = merge(l, r->lch);
		return update(r);
	}
}
pair<node*, node*> split(node *t, int k) {
	if (t == nullptr) return make_pair(nullptr, nullptr);
	if (k <= count(t->lch)) {
		pair<node*, node*> s = split(t->lch, k);
		t->lch = s.second;
		return make_pair(s.first, update(t));
	}
	else {
		pair<node*, node*> s = split(t->rch, k - count(t->lch) - 1);
		t->rch = s.first;
		return make_pair(update(t), s.second);
	}
}
node *insert(node *t, int k, int v) {
	pair<node*, node*> s = split(t, k);
	node *r = merge(s.first, new node(v));
	r = merge(r, s.second);
	return r;
}
node *erase(node *t, int k) {
	pair<node*, node*> s1 = split(t, k), s2 = split(s1.second, 1);
	if (s2.first != nullptr) delete s2.first;
	return merge(s1.first, s2.second);
}
node *find(node *t, int k) {
	if (t == nullptr) return t;
	int c = count(t->lch);
	return k < c ? find(t->lch, k) : k == c ? t : find(t->rch, k - (c + 1));
}
int find(node *t, int l, int r) {
	if (t == nullptr) return id;
	if (r < 0 || l >= count(t)) return id;
	if (l <= 0 && r >= count(t)) return t->all;
	int c = count(t->lch);
	return merge(t->lch == nullptr ? id : find(t->lch, l, r), merge(l <= c && c < r ? t->val : id, t->rch == nullptr ? id : find(t->rch, l - (c + 1), r - (c + 1))));
}
int cnt(node *t, int v) {
	if (t == nullptr) return 0;
	if (t->val < v) return count(t->lch) + 1 + cnt(t->rch, v);
	if (t->val == v) return count(t->lch);
	return cnt(t->lch, v);
}
void print(node *t) {
	if (t == nullptr) return;
	print(t->lch);
	printf(" %d", t->val);
	print(t->rch);
}
node *shift(node *t, int l, int r) {
	pair<node*, node*> s1 = split(t, l), s2 = split(s1.second, r - l), s3 = split(s2.second, 1);
	return merge(s1.first, merge(s3.first, merge(s2.first, s3.second)));
}
void change(node *t, int k, int v) {
	if (t == nullptr) return;
	int c = count(t->lch);
	if (k < c) {
		change(t->lch, k, v);
		update(t);
	}
	else if (k > c) {
		change(t->rch, k - (c + 1), v);
		update(t);
	}
	else {
		t->val = v;
		update(t);
	}
}

int main()
{
	cin.sync_with_stdio(false);
	int n, q, x, y, z;
	cin >> n >> q;
	node *root = nullptr;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		root = insert(root, i, a);
	}
	while (q--) {
		cin >> x >> y >> z;
		if (x == 0) {
			root = shift(root, y, z);
		}
		else if (x == 1) {
			printf("%d\n", find(root, y, z + 1));
		}
		else {
			change(root, y, z);
		}
	}
	return 0;
}

Measured memory_bytes: 12640
#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<char>> grid;
    int H, W, K;
public:
    void load() {
        cin >> H >> W >> K;
        grid.assign(H, vector<char>(W));
        for (int i = 0; i < H; ++i) {
            string s; cin >> s;            
            for (int j = 0; j < W; ++j) {
                grid[i][j] = s[j];
            }
        }
    }
    
    int solve() {
        int res{0};
        for (int mask_r = 0; mask_r < (1 << H); ++mask_r) {
            for (int mask_c = 0; mask_c < (1 << W); ++mask_c) {
                int cnt{0};
                for (int i = 0; i < H; ++i) {
                    for (int j = 0; j < W; ++j) {
                        if ((((mask_r >> i) & 1) == 0) && (((mask_c >> j) & 1) == 0) && grid[i][j] == '#') {                            
                            cnt++;
                        }
                    }
                }
                if (cnt == K) {
                    res++;
                }
            }            
        }
        return res;
    }
};

int main() {
    Solution sol;
    sol.load();
    cout << sol.solve() << endl;
}


Measured memory_bytes: 3148
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int W, H;
  while (cin >> W >> H, W) {
    vs v(H);
    rep(i, H) cin >> v[i];
    vvi dp(H, vi(W));
    int b = 0, w = 0;
    rep(i, H) rep(j, W) {
      dp[i][j] = 2 * (v[i][j] == 'B') + (v[i][j] == 'W');
      b -= v[i][j] == 'B';
      w -= v[i][j] == 'W';
    }
    rep(_, W * H) rep(i, H) rep(j, W) {
      if (v[i][j] != '.') continue;
      if (i > 0) dp[i][j] |= dp[i - 1][j];
      if (j > 0) dp[i][j] |= dp[i][j - 1];
      if (i < H - 1) dp[i][j] |= dp[i + 1][j];
      if (j < W - 1) dp[i][j] |= dp[i][j + 1];
    }
    rep(i, H) rep(j, W) {
      b += dp[i][j] == 2;
      w += dp[i][j] == 1;
    }
    cout << b << ' ' << w << endl;
  }
}

Measured memory_bytes: 3104
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	ll ans = 1;
	rep(i, 2) if(a[i] != a[i+1]) ans++;
	cout << ans << endl;
}


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

#define ll long long
#define ull unsigned long long

#define vi vector < int >
#define vll vector < ll >
#define vs vector < string >

#define pii pair < int, int >
#define pll pair < ll, ll >

#define pb push_back

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

int main()
{
    fast;

    ll n;

    cin >> n;

    ll cs[15], p = 1;

    memset(cs, 0, sizeof(cs));

    for(int i = 1; i < 12; i++) p *= 26, cs[i] = p + cs[i - 1];

//    for(int i = 1; i < 12; i++) cout << cs[i] << ' ';
//    cout << endl;

    int l = lower_bound(cs + 1, cs + 12, n) - cs;

    //cout << l << endl;

    n -= cs[l - 1];

    string s = "";

    for(int i = l; i > 0; i--){
        ll tmp = 1, sum = 0;

        for(int j = 1; j < i; j++) tmp *= 26;

        for(char j = 'a'; j <= 'z'; j++){
            sum += tmp;

            if(sum >= n){
                s += j;
                n -= (sum - tmp);
                break;
            }
        }
    }

    //reverse(s.begin(), s.end());

    cout << s << endl;

    return 0;
}




Measured memory_bytes: 3648
while True:
    m, f, r = map(int, input().split())
    if m == -1 and f == -1 and r == -1:
        break
    else:
        if m == -1 or f == -1:
            print('F')
        elif m + f >= 80:
            print('A')
        elif m + f >= 65:
            print('B')
        elif m + f >= 50:
            print('C')
        elif m + f >= 30:
            if r >= 50:
                print('C')
            else:
                print('D')
        else:
            print('F')


Measured memory_bytes: 5592
//#include <bits/stdc++.h>
#include <iostream>
#include<vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <string.h>
using namespace std;

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

//example rep(i,n) cin >> h[i];

int main (){

int n,cnt,q;
  cnt=0;
  q=0;

// cout<<"Hellow worldy yes"<<endl;
 
  cin>>n;
  
  if(n%2==0){
    n=n/2;
    for(int i=n-1;i>0;i--){
      cnt++;
    }
      cout<<cnt<<endl;
  }
  else{
    double num=n;
    num=num/2;
    q=(int)num;
  	for(int i=q;i>0;i--){
	  cnt++;
  
  

    }
  cout<<cnt<<endl;
    }
  //sort(vec.begin(),vec.end());
  //reverse(vec.begin(),vec.end());

  
 return 0; 
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)+1 for x in input().strip().split()]
    Dh, Dw = [int(x)+1 for x in input().strip().split()]
    M = [0 for _ in range(H+4)]
    M[0] = ['#'] * (W+4)
    M[1] = ['#'] * (W+4)
    M[-2] = ['#'] * (W+4)
    M[-1] = ['#'] * (W+4)
    for h in range(2, H+2):
        M[h] = ['#'] * 2 + list(input().strip()) + ['#'] * 2
        # print(M[h])
    ans = 0
    q = set([(Ch, Cw)])
    M[Ch][Cw] = '#'
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Dh and w == Dw:
                    print(ans)
                    return True
                newq.add((h, w))
                for dh, dw in dhdw:
                    if M[h+dh][w+dw] == '#':
                        continue
                    q_.add((h+dh, w+dw))
                    M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Measured memory_bytes: 19092
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<tuple>


#define MOD 1000000007
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back

using namespace std;

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

int main(){
    double W,H,x,y;
    cin>>W>>H>>x>>y;
    if((W/2)==x && (H/2)==y){
        cout<<(W*H/2)<<" "<<1;
    }
    else{
        cout<<(W*H)/2<<" "<<0;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,M;
  cin >> N >> M;
  int dp[100010];
  for(int i=1;i<=N;i++){
    dp[i]=1;
  }
  bool visited[100010];
  visited[1]=true;
  int x,y;
  for(int i=1;i<=M;i++){
    cin >> x >> y;
    dp[x]--;
    dp[y]++;
    if(visited[x]==true){
      visited[y]=true;
    }
    if(dp[x]==0){
      visited[x]=false;
    }
  }
  int ans=0;
  for(int i=0;i<=N;i++){
    if(visited[i])ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    int n, m;
    cin >> n >> m;
    int left = 1, right = n;
    for (int i = 0, l, r; i < m; i++) {
        cin >> l >> r;
        left = max(left, l);
        right = min(right, r);
    }
    cout << max(0, right - left + 1) << endl;
}

Measured memory_bytes: 256
(stdin => {
  // Define Function
  // Declare Variable
  const inputs = stdin.toString().trim().split(' ')
  const a = parseInt(inputs[0], 10)
  
  const b = parseInt(inputs[1], 10)
  
  const Area = (a, b) => a * b
  
  const Surr = (a, b) => (a + b) * 2


  console.log(`${Area(a, b)} ${Surr(a, b)}`)
})(require('fs').readFileSync('/dev/stdin', 'utf8'))



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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k;
  ll R,S,P;
  cin >> n >> k;
  cin >> R >> S >> P;
  string t;
  cin >> t;
  
  ll ans = 0;
  rep(i,k){
    ll dp[2][3];
    memset(dp,0,sizeof(dp));
    ll idx = 0;
    if(t[i] == 'r'){
      dp[0][0] = 0;
      dp[0][1] = 0;
      dp[0][2] = P;
    }else if (t[i] == 's'){
      dp[0][0] = R;
      dp[0][1] = 0;
      dp[0][2] = 0;
    }else {//p
      dp[0][0] = 0;
      dp[0][1] = S;
      dp[0][2] = 0;
    }
    
    while((i+k*(idx+1)) < n){
      if(t[i+k*(idx+1)] == 'r'){
        dp[(idx+1)%2][0] = max(dp[idx%2][1],dp[idx%2][2]);
        dp[(idx+1)%2][1] = max(dp[idx%2][0],dp[idx%2][2]);;
        dp[(idx+1)%2][2] = P + max(dp[idx%2][0],dp[idx%2][1]);
      }else if (t[i+k*(idx+1)] == 's'){
        dp[(idx+1)%2][0] = R + max(dp[idx%2][1],dp[idx%2][2]);
        dp[(idx+1)%2][1] = max(dp[idx%2][0],dp[idx%2][2]);;
        dp[(idx+1)%2][2] = max(dp[idx%2][0],dp[idx%2][1]);
      }else {//p
        dp[(idx+1)%2][0] = max(dp[idx%2][1],dp[idx%2][2]);
        dp[(idx+1)%2][1] = S + max(dp[idx%2][0],dp[idx%2][2]);;
        dp[(idx+1)%2][2] = max(dp[idx%2][0],dp[idx%2][1]);
      }
      idx++;
    }
    ans += max(dp[idx%2][0],max(dp[idx%2][1],dp[idx%2][2]));
    // cerr << dp[idx%2][0] << " " << dp[idx%2][1] << " " << dp[idx%2][2] << endl;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
require 'set'
while 1
    n, m = gets.split.map(&:to_i)
    break if n == 0 && m == 0
    g = {}
    (1..n).each {|i| g[i] = []}
    m.times do
        i, j = gets.split.map(&:to_i)
        g[i] << j
        g[j] << i
    end
    color = { 1 => 0 }
    queue = [1]
    until queue.empty?
        i = queue.shift
        c = color[i]
        g[i].each do |j|
            if color[j] && color[j] != 1 - c
                queue = []
                color = nil
                break
            elsif !color[j]
                color[j] = 1 - c
                queue << j
            end
        end
    end
    ans = Set.new
    if color
        k = color.values.count(0)
        if k.even?
            ans << k / 2
        end
        if (n - k).even?
            ans << (n - k) / 2
        end
    end
    p ans.size
    puts ans.sort
end



Measured memory_bytes: 7400
n,A,B,C = map(int,input().split())
l = [int(input()) for i in range(n)]
INF = 10**9

def dfs(cur,a,b,c):
    if cur == n:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+l[cur],b,c) + 10
    ret2 = dfs(cur+1,a,b+l[cur],c) + 10
    ret3 = dfs(cur+1,a,b,c+l[cur]) + 10
    return min(ret0,ret1,ret2,ret3)

print(dfs(0,0,0,0))

Measured memory_bytes: 3064
import java.util.*;
import java.util.stream.*;

class Main{
	static Scanner s=new Scanner(System.in);
	static int gInt(){
		return Integer.parseInt(s.next());
	}
	public static void main(String[] A){
		System.out.println(
				IntStream.range(2,11110).map(i->i*5+1)
						.filter(o->IntStream.range(2,o).noneMatch(p->o%p==0))
						.limit(gInt())
						.mapToObj(String::valueOf)
						.collect(Collectors.joining(" "))
						);
	}
}


Measured memory_bytes: 25684
#![allow(non_snake_case)]
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;

#[fastout]
fn main() {
    input!{
        a: usize,
    }
    println!("{}", a + a.pow(2) + a.pow(3) );
}


Measured memory_bytes: 2168
#include <bits/stdc++.h> 
 
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int a[2][101];
int main(){
    int N;
    cin>>N;
    REP(i,2)REP(j,N)cin>>a[i][j];
    int res=0;
    REP(pos,N){
        int tmp=0;
        REP(j,N){
            if(j<pos)tmp+=a[0][j];
            else if(j==pos)tmp+=(a[0][j]+a[1][j]);
            else tmp+=a[1][j];
        }
        res=max(res,tmp);
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx,avx2,tune=native")
//#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds; 
using namespace __gnu_cxx;
using namespace std;
using ll = long long;

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define precision(n) fixed<<setprecision(n)

#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("output.txt","w",stderr);
    #endif
}
template<typename T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update >;
template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T> >;
template<typename T> void done(T ans) {cout << ans << "\n"; exit(0);}

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);

clock_t time_p=clock();
void printTime(){
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}


const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int main() {
    io();
    ll x, y;
    cin >> x >> y;
    cout << min(x % y, y - (x % y));

}




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

using namespace std;

struct Edge {
  int src, dst;
  long long weight;
  Edge(int f, int t, long long w) {
    src = f;
    dst = t;
    weight = w;
  }
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

bool conflict(Graph &g) {
  int n = g.size();
  vector<long long> dist(n);
  vector<bool> visited(n, false);
  for (int i = 0; i < n; ++i) {
    if (visited[i])
      continue;
    visited[i] = true;
    stack<int> st;
    st.push(i);
    while (!st.empty()) {
      int now = st.top();
      st.pop();
      for (auto e : g[now]) {
        if (visited[e.dst]) {
          if (dist[e.dst] != dist[now] + e.weight) {
            return 0;
          }
        } else {
          dist[e.dst] = dist[now] + e.weight;
          st.push(e.dst);
          visited[e.dst] = true;
        }
      }
    }
  }
  return 1;
}

int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n);
  for (int i = 0; i < m; ++i) {
    int l, r;
    long long d;
    cin >> l >> r >> d;
    g[l - 1].emplace_back(l - 1, r - 1, d);
    g[r - 1].emplace_back(r - 1, l - 1, -d);
  }
  if (conflict(g)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 13824
def solve():
    import sys
    from itertools import combinations
    from bisect import bisect
    from heapq import heappush, heappop
    file_input = sys.stdin
    inf = float('inf')
    while True:
        n, m, c, s, g = map(int, file_input.readline().split())
        if n == 0:
            break
        
        # Adjacency matrices recording distances for each company
        adj_matrices = [[[inf] * n for j in range(n)] for i in range(c)]
        
        for i in range(m):
            x, y, d, c = map(int, file_input.readline().split())
            mat = adj_matrices[c - 1]
            x -= 1
            y -= 1
            pre_d = mat[x][y]
            if d < pre_d:
                mat[x][y] = d
                mat[y][x] = d
        
        p = file_input.readline()
        
        # Adjacency matrix recording fare for the Dijkstra's algorithm
        adj_matrix = [[inf] * n for i in range(n)]
        
        for mat in adj_matrices:
            # Warshall–Floyd Algorithm
            for k in range(n):
                for x, y in combinations(range(n), 2):
                    d1 = mat[x][y]
                    d2 = mat[x][k] + mat[k][y]
                    if d2 < d1:
                        mat[x][y] = d2
                        mat[y][x] = d2
            
            q = list(map(int, file_input.readline().split()))
            r = list(map(int, file_input.readline().split()))
            
            # Fare calculation
            for x, y in combinations(range(n), 2):
                d = mat[x][y]
                if d != inf:
                    idx = bisect(q, d)
                    fare = 0
                    pre_sd = 0
                    for sd, f in zip(q[:idx], r):
                        fare += f * (sd - pre_sd)
                        pre_sd = sd
                    fare += r[idx] * (d - pre_sd)
                    if fare < adj_matrix[x][y]:
                        adj_matrix[x][y] = fare
                        adj_matrix[y][x] = fare
        
        # Dijkstra's algorithm
        s -= 1
        g -= 1
        fare = [inf] * n
        fare[s] = 0
        pq = [(0, s)]
        while pq:
            u_fare, u = heappop(pq)
                    
            if u == g:
                print(u_fare)
                break
            
            for v, f in enumerate(adj_matrix[u]):
                new_fare = u_fare + f
                if new_fare < fare[v]:
                    fare[v] = new_fare
                    heappush(pq, (new_fare, v))
        else:
            print(-1)

solve()


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

int main() {
	
	int n;
	cin >> n;
	vector<int> l(n);
	rep(i, n){
		cin >> l[i];
	}
	sort(l.begin(), l.end());
	int sum = 0;
	for(int i = 0; i < n-1; i++){
		sum += l[i];		
	}
	if(l[n-1] >= sum) puts("No");
	else puts("Yes");
	
	return 0;
}

Measured memory_bytes: 256
import queue
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1

def isbridge(j):
    G=[set() for i in range(N)]
    for i in range(M):
        if i==j:
            continue
        G[a[i]].add(b[i])
        G[b[i]].add(a[i])
    q=queue.Queue()
    reached=[0 for i in range(N)]
    q.put(0)
    reached[0]=1
    while(not(q.empty())):
        r=q.get()
        reached[r]=1
        for p in G[r]:
            if reached[p]==0:
                q.put(p)
    if sum(reached)==N:
        return False
    else:
        return True

ans=0
for i in range(M):
    if isbridge(i):
        ans+=1
print(ans)


Measured memory_bytes: 4072
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	LL ans = 0;
	int n;
	cin >> n;
	map<string, int> ms;
	while (n--)
	{
		string str;
		cin >> str;
		sort(str.begin(), str.end());
		ans += ms[str]++;
	}
	cout << ans << endl;
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define fin(x) cout << x << endl;

using namespace std;
using ll = long long;

int main(void) {
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << " " << x << " " << y << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
#include<cassert>

#define REP(i, b, n) for(int i =b; i<(int) n; i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++it)

using namespace std;

enum{
  H = 501, N = 101, KK = 101
};

int h, n, p, m, K;
double dp[H][N][KK];
bool usedHeight[H], canMove[H][N];
int atl[H];
double solve(int cnt){
  rep(i, H)rep(j, N)rep(k, KK)dp[i][j][k] = 0;
  dp[h][p-1][0] = 1;
  for(int i = h; i>0; i--){
    rep(j, n){
      rep(k, K+1){
        //cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k]<< endl;;
        if(canMove[i][j-1]){
          dp[i-1][j-1][k] += dp[i][j][k];
        }
        else if(canMove[i][j]){
          dp[i-1][j+1][k] += dp[i][j][k];
        }
        else if(!usedHeight[i] && k < K){
          int tmp=n-1;
          if(j > 0){//left
            dp[i-1][j-1][k+1] += dp[i][j][k]; 
            tmp--;
          }
          if(j < n-1){//right
            dp[i-1][j+1][k+1] += dp[i][j][k];
            tmp--;
          }
          
          //mid
          //dp[i-1][j][k] += dp[i][j][k] * remain;
          //if (k+i-1 >= K){

          if (k+atl[i] > K){
            dp[i-1][j][k+1]+=dp[i][j][k]*tmp;
            dp[i-1][j][k]  +=dp[i][j][k];// * remain;
          }else {
            dp[i-1][j][k+1]+=dp[i][j][k]*tmp;
          }
        }
        else {
          dp[i-1][j][k] += dp[i][j][k];
        }
      }
    }       
  }
  double ret = 0,sum=0;
  rep(i, n){
    ret = max(ret, dp[0][i][K]);
    sum+=dp[0][i][K];
  }
  //cout << endl;
  //cout <<"proba sum " <<  sum << endl;
  return ret/sum;
}

int main(){
  while(cin >> h >> n >> p >> m >> K){
    rep(i, H+1){
      usedHeight[i] = false;
      rep(j, N){
        canMove[i][j] = false;
      }
    }
    rep(i, m){
      int a, b;
      cin >> a >> b;
      canMove[a][b-1] = true;
      usedHeight[a] = true;
    }
    rep(i,H+1)atl[i]=0;
    REP(i,1,H+1){
      atl[i]+=atl[i-1];
      if (!usedHeight[i])atl[i]++;
    }

    int cnt = (h - m ) * (n-1);
    printf("%.10f\n", solve(cnt));
  }

}

Measured memory_bytes: 39000
#include<iostream>
using namespace std;
int main(){
	char ch;
	int n,m;
	bool ar[4][13];
	for(int i=0;i<4;i++) {
		for(int j=0;j<13;j++)
			ar[i][j]=false;
	}
	cin >> m;
	while(m-->0){
	cin >> ch >> n;
		switch (ch)
		{
			case 'S':
					ar[0][n-1]=true;
					break;
			case 'C':
					ar[2][n-1]=true;
					break;
			case 'D':
					ar[3][n-1]=true;
					break;
			case 'H':
					ar[1][n-1]=true;
				break;
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<13;j++)
			if(ar[i][j]==false){
				if(i==0)
					cout <<"S ";
				else if(i==1)
					cout <<"H ";
				else if(i==2)
					cout <<"C ";
				else
					cout <<"D ";
				cout <<j+1<<endl;;
			}
	}
	return 0;
}

Measured memory_bytes: 3100
#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);
  
  string s;
  while (cin >> s) {
    vector<int> prev, next;
    for (int i = 0; i < 10; i++) {
      prev.emplace_back(s[i] - '0');
    }
    while (prev.size() > 1) {
      next.clear();
      for (int i = 0; i + 1 < (int)prev.size(); i++) {
        next.emplace_back((prev[i] + prev[i + 1]) % 10);
      }
      swap(prev, next);
    }
    cout << prev[0] << endl;
  }

  return 0;
}


Measured memory_bytes: 3104
n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

for j in range(1, n-1):
    for i in range(j):
        k = 2*j - i
        if k<n and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
            ans -= 1
print(ans)

Measured memory_bytes: 9112
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n,ans;
  cin>>n;
  int p[n];
  for(int i=0;i<n;i++){
    cin>>p[i];
  }
  sort(p,p+n);
  for(int i=0;i<n;i++){
ans+=p[i];
  }
  cout<<ans-p[n-1]/2<<endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var (
		a int
		b int
		c int
	)
	fmt.Scan(&a, &b, &c)

	lhs := c - (a + b)
	d := lhs*lhs - 4*a*b

	if lhs <= 0 || d <= 0 {
		fmt.Print("No")
	} else {
		fmt.Print("Yes")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

ll a[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	ll ans = a[1], id = 2;
	for(ll i = 2; i <= n - 1; i += 2)
	{
		ans += a[id];
		if(i + 1 < n)
		ans += a[id];
		id ++;
	}
	cout << ans << '\n';





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 5184
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int nxt[100005];
int dist[100005];

signed main()
{
    int N; cin>>N;
    REP(i,N){
        cin>>nxt[i]; nxt[i]--;
        dist[i]=-1;
    }
    dist[0]=0;

    int cur=0;
    while(true){
        if(dist[nxt[cur]]!=-1) break;
        dist[nxt[cur]]=dist[cur]+1;
        cur=nxt[cur];
    }
    cout<<dist[1]<<endl;
 
}


Measured memory_bytes: 1792
# _*_ coding:utf-8 _*_
#  Atcoder_Beginners_Contest121-B
#  TODO https://atcoder.jp/contests/abc121/tasks/abc121_b

# 20190309直接計算した方が速いので試験以内では省略
# def solveProblem(YYYYY):
#	answer = YYYYY
#	return answer


if __name__ == '__main__':
	N,M,C = map(int,input().strip().split(' '))
	blist = list(map(int,input().strip().split(' ')))
	counter = 0
	for _ in range(0,N,+1):
		saiten = 0
		alist = list(map(int,input().strip().split(' ')))
		for i in range(0,M,+1):
			saiten = saiten + blist[i]*alist[i]
		saiten = saiten + C
		if 0 < saiten :
			counter = counter + 1

	solution = counter
	print("{}".format(solution))


Measured memory_bytes: 3064
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
long long b[3][100000];
int main(void)
{
	int n,i,j,a[3][100001],p;
	long long sum,cnt;
	scanf("%d",&n);
	for(i=0;i<3;i++)	{
		for(j=0;j<n;j++)	{
			scanf("%d",&a[i][j]);
		}
		a[i][n]=2000000000;
		sort(a[i],a[i]+n+1);
	}
	for(i=0;i<n;i++)	b[0][i]=1;
	for(i=1;i<3;i++)	{
		cnt=0;	p=0;
		for(j=0;j<n;j++)	{
			while(a[i][j]>a[i-1][p])	{
				cnt+=b[i-1][p];
				p++;
			}
			b[i][j]=cnt;
//			printf("b=%d\n",cnt);
		}
	}
	sum=0;
	for(i=0;i<n;i++)	sum+=b[2][i];
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}
 
 
 
 
 
 
 




vector<pair<int,int>> adj[100005];
ll dist[100005];
int n;
void dfs(int node,int par){
     for(auto ch:adj[node]){
          if(ch.fi==par)continue;
          dist[ch.fi]=dist[node]+ch.se;
          dfs(ch.fi,node);
     }
}




int main()
{
    string s;
    cin>>s;
    ll dp[15]={0};
    if(s[0]=='?'){
         for(int i=0;i<10;i++)dp[i]=1;
    }
    else dp[s[0]-'0']=1;
    for(int i=1;i<s.length();i++){
         ll tmp[15]={0};
         if(s[i]=='?'){
              for(int j=0;j<10;j++){
                   for(int k=0;k<13;k++){
                        if(dp[k]>0){
                             int rem=(k*10+j)%13;
                             tmp[rem]=(tmp[rem]+dp[k])%mod;
                        }
                   }
              }
         }
         else{
              int d=s[i]-'0';
              for(int j=0;j<13;j++){
                   if(dp[j]>0){
                        int rem=(j*10+d)%13;
                        tmp[rem]=(tmp[rem]+dp[j])%mod;
                   }
              }
         }
         for(int j=0;j<13;j++)dp[j]=tmp[j];
         
    }
    cout<<dp[5];
    

}



































Measured memory_bytes: 6068
import sys

input = sys.stdin.readline
INF = float("inf")


def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * N
    for i in range(1, N):
        min_cost = INF
        for k in range(1, min(K + 1, i + 1)):
            cost = dp[i - k] + abs(h[i] - h[i - k])
            if cost < min_cost:
                min_cost = cost
        dp[i] = min_cost

    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


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

int main(){
  int N;
  cin >> N;
  
  int sum = 0;
  int num = N;
  for (int i = 0; i < 8; i++){
    sum += num % 10;
    num = num / 10;
    if (num == 0) break;
  }
  
  if (N % sum == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main() {
  int N;
  vector<int> n(4);
  cin >> N;
  for (int i=0; i<4; i++) {
    n[i]=N%10;
    N/=10;
  }
  reverse(n.begin(),n.end());
  
  int sum;
  int bit;
  for (bit=0; bit<(1<<3); bit++) {
    sum=n[0];
    for (int j=0; j<3; j++) {
      if (bit & (1<<j))
	sum+=n[j+1];
      else
	sum-=n[j+1];
    }
    if (sum==7)
      break;
  }
 
  for (int i=0; i<3; i++) {
    cout << n[i];
    if (bit & 1<<i)
      cout << '+';
    else
      cout << '-';
  }
  cout << n[3] << "=7" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define A cout << "Audrey wins." << endl
#define F cout << "Fabre wins." << endl

int c2i(char s){
  return s-'0';
}

string c2s(char aa,char bb){
  int a = c2i(aa)+c2i(bb);
  if(a == 0) return "0";

  string s = "";
  while(a > 0){
    s += ((a%10)+'0');
    a /= 10;
  }
  reverse(s.begin(),s.end());
  return s;
}

int main(){
  int n;

  cin >> n;
  while(n--){
    string str;
    cin >> str;
    
    int cnt = 0;
    while(str.size() >= 2){
      cnt++;
      int pos = str.size()-2;
      string tmp = c2s(str[pos],str[pos+1]);
      if(pos >= 0) str = str.substr(0,pos) + tmp;
    }
    if(cnt%2) F;
    else A;    
  }
  return 0;
}

Measured memory_bytes: 1216
#c.py
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
m = lis[0]
M = lis[-1]
ans_lis = []

for now in lis[1:-1]:
    if now > 0:
        ans_lis.append([m,now])
        m -= now
    else:
        ans_lis.append([M,now])
        M -= now
ans_lis.append([M,m])
print(M-m)
for x in ans_lis:
    print(x[0],x[1])


Measured memory_bytes: 23108