akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

void dfs(map<int, int> &chara, map<int, vector<int>> &g, int start)
{
    map<int, int> visited;
    deque<pair<int, int>> que;
    que.push_back({start, 0});
    while (!que.empty())
    {
        auto cur = que.front();
        que.pop_front();
        if (visited[cur.first])
            continue;
        chara[cur.first] = cur.second;
        visited[cur.first] = true;
        for (auto x : g[cur.first])
        {
            if (visited[x] == false)
            {
                que.push_back({x, cur.second + 1});
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    map<int, vector<int>> g;
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    map<int, int> fennec, snuke;
    dfs(fennec, g, 0);
    dfs(snuke, g, n - 1);
    int fnum = 0, snum = 0;
    rep(i, n)
    {

        if (fennec[i] <= snuke[i])
        {
            fnum++;
        }
        else
        {
            snum++;
        }
    }
    if (fnum > snum)
    {
        cout << "Fennec" << endl;
    }
    else
    {
        cout << "Snuke" << endl;
    }

    return 0;
}


Measured memory_bytes: 25216
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		String s=scan.next();
		//System.out.println(s.length());
		if(s.length()<=n) System.out.println(s);
		else {
			System.out.println(s.substring(0,n)+""+"...");
			}
	}

}


Measured memory_bytes: 26772
from collections import Counter as c
n,k=map(int,input().split())
a=list(map(int,input().split()))

b=sorted(c(a).items(),key=lambda x:x[1])
kind=len(c(a))
i=0
ans=0
while k<kind:
    ans+=b[i][1]
    kind-=1
    i+=1
print(ans)

Measured memory_bytes: 50100
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    int count = 0;

    rep(i, s.length()) {
        if(s[i] == t[i])
            count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  string s;
  while (cin >> s) {
    int res = s.size() - 1;
    for (char a : s) {
      string t = s;
      int cost = 0;
      while (t != string(t.size(), a)) {
        for (int i = 0; i < t.size() - 1; i++) {
          t[i] = (t[i] == a || t[i + 1] == a) ? a : t[i];
        }
        t = t.substr(0, t.size() - 1);
        ++cost;
      }
      res = min(res, cost);
    }
    cout << res << endl;
  }
  return 0;
}


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

set<int> st;
int n;
void dfs(int x)
{
    ll y = 1LL * 10 * x + 3;
    if (y > n)
        return;
    for (int i = 0; i < 5; i += 2)
        st.insert(y + i), dfs(y + i);
}
int main(void)
{
    cin >> n;
    dfs(0);
    int ans = 0;
    for (auto i : st)
    {
        int j = i;
        map<int, int> mp;
        while (j > 0)
            mp[j % 10]++, j /= 10;
        if (mp[3] == 0 || mp[5] == 0 || mp[7] == 0)
            continue;
        if (i <= n)
            ans++;
    }
    cout << ans << endl;
}


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

int main(){
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	int q;
	scanf("%d", &q);
	vector<int> b(q);
	for(int i = 0; i < q; i++)
		scanf("%d", &b[i]);
	sort(b.begin(), b.end());
	vector<int> i;
	set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(i));
	for(auto x: i)
		printf("%d\n", x);
}



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

int dp[105][4][2];

int main() {
  int a, b, c, k;
  int ans = 0; //ans=0なら失敗
  cin >> a >> b >> c;
  cin >> k;
  
  for( int i = 0 ; i < k ; i++ ){
    if(a >= b){
      b *= 2;
      continue;
    }
    
    if( a < b && b >= c  ){
      c *= 2;
    }
  }
  
  if( a < b && b < c ){
    ans = 1;
  }
  
  //printf("%d, %d, %d\n", a, b, c);
  
  if(ans == 1)cout << "Yes" << endl;
  else{
    cout << "No" << endl;
  }
  
  return 0;
  
}

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

int main() {
    size_t A, B;
    std::string S;
    std::cin >> A >> B >> S;

    for (size_t i = 0; i < S.size(); ++i) {
        if (i == A) {
            if (S[i] != '-') {
                std::cout << "No\n";
                return 0;
            }
        } else {
            if (('0' <= S[i] && S[i] <= '9') == false) {
                std::cout << "No\n";
                return 0;
            }
        }
    }

    std::cout << "Yes\n";

    return 0;
}


Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;



int main(){
   string s,t;
   cin >> s >> t;
sort(s.begin(),s.end());
sort(t.begin(), t.end());
reverse(t.begin(), t.end());
if(s < t) cout << "Yes" << endl;
else cout << "No" << endl;

}


Measured memory_bytes: 256
N,X = map(int,input().split())
L = list(map(int,input().split()))
D = [0]*(N+1)
cnt=1
for i in range(1,N+1):
    D[i] = D[i-1] + L[i-1]
    if D[i] <= X:
        cnt+=1
    else:
        break
print(cnt)

Measured memory_bytes: 38384
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<queue>
using namespace std;
 
priority_queue<int>QD;
priority_queue<int,vector<int>,greater<int> >QU;
 
typedef long long ll;
int n;
int a[310000];
ll pmx[310000],qmn[310000],smx,smn,ans=-(1ll<<60);
 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=3*n;i++){
        scanf("%d",&a[i]);
    }for(int i=1;i<=n;i++){
        smx+=a[i];
        QU.push(a[i]);
    }
    pmx[n]=smx;
    for(int i=n+1;i<=3*n;i++){
        if(a[i]>QU.top()){
            smx-=QU.top();
            QU.pop();
            smx+=a[i];
            QU.push(a[i]);
        }
        pmx[i]=smx;
    }
    for(int i=3*n;i>2*n;i--){
        smn+=a[i];
        QD.push(a[i]);
    }
    qmn[2*n+1]=smn;
    for(int i=2*n;i;i--){
        if(a[i]<QD.top()){
            smn-=QD.top();
            QD.pop();
            smn+=a[i];
            QD.push(a[i]);
        }
        qmn[i]=smn;
    }
    for(int i=n;i<=2*n;i++){
        ans=max(ans,pmx[i]-qmn[i+1]);
    }
    printf("%lld\n",ans);
    return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    int X = max(max(A, B), C); // A B Cが X に揃ったとする
    if ((3 * X % 2) != ((A + B + C) % 2)) X++; // 操作でA+B+Cの偶奇は変わらないのでX+X+Xとの偶奇が合わない場合は+1する

    int ans = (3 * X - (A + B + C)) / 2; // 1回の操作で総和が+2されるので,差分を2で割った数が操作回数
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
 
int main(){
        int o,i,out=0,b=0,p[100];
        string ev;
        
        cin >> o;
 
        for(i=0; i<o; i++){
 
                p[i] = 0;
 
                while(1){
 
                        cin >> ev;
                        
                        if(ev=="HIT"){
                                b++;
                                
                                if(b==4){
                                        b--;
                                        
                                        p[i]++;
                                }
                        }
                        
                        else if(ev=="HOMERUN"){
                                p[i] += b+1;
                                
                                b=0;
                        }
                        
                        else if(ev=="OUT"){
                                out++;
                        }
 
                        if(out==3) break;
                }
                
                out=0;
                b=0;
        }
 
        for(i=0; i<o; i++){
                cout << p[i] << endl;
        }
 
  return 0;
}
 

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define pb push_back
#define vl vector
#define ff first
#define ss second
using namespace std;
int main()
{
    ll a,b,i,j,n,t,c;
    cin>>a>>b>>c;
    a=a-b;
    c-=a;
    if(c<0) cout<<"0";
    else cout<<c;
}

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


struct xy{
  double  x,y;
};

void Koch(int n,xy p1,xy p2){
  if(n==0)return ;
xy s,t,u;
  s.x=(2*p1.x+p2.x)/3;
  s.y=(2*p1.y+p2.y)/3;
  t.x=(p1.x+2*p2.x)/3;
  t.y=(p1.y+2*p2.y)/3;
  u.x=(t.x-s.x)/2-(t.y-s.y)*(sqrt(3.0)/2)+s.x;
  u.y=(t.x-s.x)*(sqrt(3.0)/2)+(t.y-s.y)/2+s.y;

  Koch(n-1,p1,s);
  printf("%f %f\n",s.x,s.y);
  Koch(n-1,s,u);
  printf("%f %f\n",u.x,u.y);
  Koch(n-1,u,t);
  printf("%f %f\n",t.x,t.y);
  Koch(n-1,t,p2);
}


int main(){
  int n;
  cin>>n;
  xy p1,p2;
  p1.x=0,p1.y=0;
  p2.x=100,p2.y=0;
  printf("%f %f\n",p1.x,p1.y);
  Koch(n,p1,p2);
  printf("%f %f\n",p2.x,p2.y);
  return 0;
}



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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    string S;
    cin >> S;
    ll maxi = 0;
    ll temp = 0;
    rep(i, 3) {
        if(S[i] == 'R') temp++;
        else maxi = max(maxi, temp), temp = 0;
    }
    maxi = max(maxi, temp);
    cout << maxi << endl;
    return 0;
}


Measured memory_bytes: 3620
import sys

sys.setrecursionlimit(4100000)

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')    

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

struct segmentTree{

    int N;
    vector<long long> node;
    const long long INF = LLONG_MIN;
    
    void init(int siz){
        N = 1;
        while(N < siz){
            N <<= 1;
        }
        node.resize(N * 2 - 1, INF);
    }

    void build(vector<long long> &dat){
        for(int i = 0, len = dat.size() ; i < len ; ++i){
            node[i + N - 1] = dat[i];
        }
        for(int i = N - 2 ; i >= 0 ; --i){
            node[i] = max(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    void update(int k, long long x){
        k += N - 1;
        node[k] = x;
        while(k > 0){
            k = (k - 1) / 2;
            node[k] = max(node[k * 2 + 1], node[k * 2 + 2]);
        }
    }

    long long getMax(int a, int b, int k, int l, int r){
        if(r <= a || b <= l){
            return INF;
        }
        if(a <= l && r <= b){
            return node[k];
        }
        long long vl = getMax(a, b, k * 2 + 1, l, (l + r) / 2);
        long long vr = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
        return max(vl, vr);
    }

    long long getMax(int a, int b){
        return getMax(a, b, 0, 0, N);
    }

};

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n){
        cin >> h[i];
    }
    vector<lint> a(n);
    rep(i, n){
        cin >> a[i];
    }
    vector<lint> dp(n + 1, 0);
    segmentTree st;
    st.init(n + 1);
    st.build(dp);
    lint ans = 0;
    rep(i, n){
        dp[h[i]] = max(dp[h[i]], st.getMax(0, h[i]) + a[i]);
        st.update(h[i], dp[h[i]]);
        ans = max(ans, dp[h[i]]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, L;
  cin >> N >> L;
  int count = 0;
  
  if(L > 0){
    for(int i = 0; i < N; i++){ 
      count += L + i;
    }
    count -= L;
  }
  
  else if(L + N - 1 < 0){
    for(int i = 0; i < N; i++){ 
      count += L + i;
    }
    count -= L + N - 1;
  }
  else{
    for(int i = 0; i < N; i++){ 
      count += L + i;
    }
    }
  cout << count << endl;
}


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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

vector<int> niz;
vector<int> pniz;
vector<tuple<int, int, int>> res;
int n, duz;

void dabl()
{
    n++;
    res.pb(mt(n-1, n, duz));
    res.pb(mt(n-1, n, 0));
    duz *= 2;
}

void dodaj()
{
    res.pb(mt(1,n,duz));
    duz++;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int l;
    cin >> l;
    while(l > 0) niz.pb(l%2), l/=2;

    for(int i = niz.size()-1; i >= 0; i--)
        pniz.pb(niz[i]);

    res.pb(mt(1,2,0));

    duz = 1;
    n = 2;

    for(int i = 1; i < pniz.size(); i++)
    {
        if(i == 1) dodaj();
        else dabl();
        if(pniz[i] == 1) dodaj();
    }
    cout << n << " " << res.size() << "\n";
    for(int i = 0; i < res.size(); i++)
        cout << get<0>(res[i]) << " " << get<1>(res[i]) << " " << get<2>(res[i]) << "\n";

    return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
steps = list(map(int, input().split()))
costs = [0]*(N+1)
for i in range(1, N):
  if i<=K:
    k = i
  choices = [costs[i-j] + abs(steps[i]-steps[i-j]) for j in range(1, k+1)]
  costs[i] = min(choices)
print(costs[N-1])

Measured memory_bytes: 52448
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcd(ll a,ll b)
{
    if(a==0)
        return b;
    if(b==0)
        return a;
    return gcd(b%a,a);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   // ifstream cin("/Users/rajdeepdhingra/Downloads/82.txt");
    ll n,m;
    cin>>n>>m;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        a[i] = a[i]>>1;
    }
  //  cout<<a[n-1]<<"\n";
    ll r = a[0];
    for(ll i=1;i<n;i++)
    {
        ll gc;
        gc = gcd(r,a[i]);
      //  cout<<gc<<endl;
        r = (r*a[i])/gc;
        if(r>m)
        {
            cout<<0<<"\n";
            return 0;
        }
    }
//    cout<<r<<endl;
//    cout<<r/a[n-1]<<endl;
    bool pos=1;
    for(ll i=0;i<n;i++)
    {
        ll yup;
        yup = r/a[i];
        if(!(yup&1))
        {
            pos=0;
            cout<<0<<"\n";
            return 0;
        }
    }
    ll yup;
    yup = m/r;
    yup++;
    yup=yup>>1;
    cout<<yup<<"\n";
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        System.out.println((long)((1900*m+100*(n-m))*Math.pow(2,m)));
    }
}

Measured memory_bytes: 24916
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

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

        int min = 1000000000;
        for(int i=0; i+k-1<n; i++) {
            int left =x[i];
            int right = x[i+k-1];
            int d = 1000000000;
            if(right < 0) {
                d = -left;
            } else if(left<0){
                d = Math.min(-left * 2 + right, -left + right * 2);
            } else {
                d = right;
            }
            min = Math.min(min, d);
        }

        System.out.println(min);
    }

}


Measured memory_bytes: 50196
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;

typedef long long int64;
const int inf = (int)1e9;

int tobit(int x[5])
{
	int ret = 0;
	
}

int main()
{
	int testcase;
	
	scanf("%d", &testcase);
	
	for(int testnum = 0; testnum < testcase; ++testnum) {
		
		int start[5][5];
		bool emp[5][5] = {false};
		
		for(int y = 0; y < 5; ++y) {
			for(int x = 0; x < 5; ++x) {
				scanf("%d", start[x] + y);
				start[x][y] -= 1;
				if(start[x][y] == -1) {
					start[x][y] = 0;
					emp[x][y] = true;
				}
			}
		}
		
		int dp[5][1 << 10] = {0};
		const int point[] = {0, 60, 70, 80};
		
		fill(dp[0], dp[5], -1);
		
		int startbit = 0;
		int startpoint = 0;
		for(int i = 0; i < 5; ++i) {
			startbit |= start[0][i] << (i * 2);
			startpoint += point[start[0][i]];
		}
		dp[0][startbit] = startpoint;
		
		for(int col = 0; col < 4; ++col) {
			
			for(int state = 0; state < (1 << 10); ++state) {
				
				if(dp[col][state] == -1)
					continue;
				
				int statepoint = 0;
				for(int i = 0; i < 5; ++i)
					statepoint += !emp[col][i] * point[(state >> (i * 2)) & 3];
			
				for(int button = 0; button < (1 << 8); ++button) {
					
					int cur[5] = {0};
					int next[5] = {0};
					
					for(int i = 0; i < 5; ++i) {
						cur[i] = (state >> (i * 2)) & 3;
						next[i] = start[col + 1][i];
					}
					
					for(int i = 0; i < 4; ++i) {
						int push = (button >> (i * 2)) & 3;
						next[i] = (next[i] + push) & 3;
						next[i + 1] = (next[i + 1] + push) & 3;
						cur[i] = (cur[i] + push) & 3;
						cur[i + 1] = (cur[i + 1] + push) & 3;
					}
					
					int nextbit = 0;
					int nextpoint = dp[col][state] - statepoint;
					
					for(int i = 0; i < 5; ++i)
						nextbit |= next[i] << (i * 2);
					for(int i = 0; i < 5; ++i) {
						nextpoint += !emp[col][i] * point[cur[i]];
						nextpoint += !emp[col + 1][i] * point[next[i]];
					}
					
					dp[col + 1][nextbit] = max(dp[col + 1][nextbit], nextpoint);
				}
			}
		}
		
		int ans = 0;
		
		for(int i = 0; i < (1 << 10); ++i)
			ans = max(ans, dp[4][i]);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

/* ハラスメントに負けず */
/* 0完太陽にも負けず */
/* はやく人権を獲得したい */
/* nullmineralが書きましたが */
/* 責任はまったくとりません */

Measured memory_bytes: 1216
import static java.lang.System.*;
import java.util.*;

public class Main {
	static int[] par;
	static int[] rank;
	
	public static void UnionFindTree(int size) {
		par = new int[size];
		rank = new int[size];
		for (int i = 0; i < size; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	public static void union(int x, int y) {
		int xroot = find(x);
		int yroot = find(y);
		
		if (rank[xroot] > rank[yroot]) par[yroot] = xroot;
		else if(rank[xroot] < rank[yroot]) par[xroot] = yroot;
		else if (xroot != yroot){
			par[yroot] = xroot;
			rank[xroot]++;
		}
	}
	
	public static int find(int i) {
		//out.println(i + " " + par[i]);
		if (i != par[i]) par[i] = find(par[i]);
		return par[i];
	}
	
	public static boolean same(int x, int y) {
		//out.println(" " + x + " " + y);
		return find(x) == find(y);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] num = new int[n];
		for(int i=0; i<n; i++) num[i] = sc.nextInt();
		
		int[] x = new int[m];
		int[] y = new int[m];
		for(int i=0; i<m; i++) {
			x[i] = sc.nextInt()-1;
			y[i] = sc.nextInt()-1;
		}
		
		UnionFindTree(n);
		for(int i=0; i<m; i++) union(x[i], y[i]);
		
		//for(int i=0; i<n; i++) out.println(par[i]);
		
		int count=0;
		for(int i=0; i<n; i++) {
			if(same(i, num[i]-1)) count++;
		}
		
		out.println(count);
	}

}


Measured memory_bytes: 90260
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var mod = 1e9+7;
function mul(){for(var a=arguments,r=a[0],i=a.length;--i;)r=((r>>16)*a[i]%mod*65536+(r&65535)*a[i])%mod;return r;}
var fac=[],finv=[],invs=[],pow2=[];
function fset(n){
  fac.length=n+1,fac[0]=fac[1]=1;
  for(var i=2;i<=n;)fac[i]=mul(fac[i-1],i++);
  finv.length=n+1,finv[0]=finv[1]=1,finv[n]=inv(fac[n]);
  for(i=n;2<i;)finv[i-1]=mul(finv[i],i--);
  invs.length=n+1,invs[0]=invs[1]=1;
  for(i=2;i<=n;)invs[i]=mul(fac[i-1],finv[i++]);
  pow2.length=n+1,pow2[0]=1;
  for(i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
}
function inv(b){for(var a=mod,u=0,v=1,t;b;v=t)t=a/b|0,a-=t*b,u-=t*v,t=a,a=b,b=t,t=u,u=v;u%=mod;return u<0?u+mod:u;}
function pow(a,n){for(var r=1;n;a=mul(a,a),n>>=1)if(n&1)r=mul(a,r);return r;}
function ncr(n,r){return mul(fac[n],finv[r],finv[n-r]);}
function npr(n,r){return mul(fac[n],finv[r]);}

console.log(main());
function main(){
  var n = o.a(), k = o.a();
  if(k === 1)return 0;
  var a = o.l().sort((a,b)=>a-b);
  a = a.map(a=>(a+1e9)%mod);
  fset(n);
  var ans = 0;
  for(var i = 0; i < n-k+1; i++){
    ans -= mul(a[i],ncr(n-i-1,k-1));
  }
  for(var i = k-1; i < n; i++){
    ans += mul(a[i],ncr(i,k-1));
  }
  ans %= mod;
  ans += mod;
  return ans%mod;
}

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

int main() {
    int n, m; scanf("%d%d", &n, &m);
    constexpr int kMod = 998244353;
    vector<int> fc(3 * m + n, 1), iv(3 * m + n, 1);

    auto fpow = [&](int a, int n) {
        int res = 1;
        while (n > 0) {
            if (n & 1) res = 1LL * res * a % kMod;
            a = 1LL * a * a % kMod;
            n >>= 1;
        }
        return res;
    };

    for (int i = 1; i < fc.size(); ++i) {
        fc[i] = 1LL * fc[i - 1] * i % kMod;
        iv[i] = fpow(fc[i], kMod - 2);
    }

    auto Choose = [&](int n, int k) {
        if (n < k || k < 0) return 0LL;
        return 1LL * fc[n] * iv[k] % kMod * iv[n - k] % kMod;
    };

    int ans = 0;
    for (int i = 0; i <= m; ++i) {
        if ((3 * m - i) % 2 != 0) continue;
        ans += 1LL * Choose((3 * m - i) / 2 + n - 1, n - 1) * Choose(n, i) % kMod;
        ans %= kMod;
    }

    vector<int> a(m), b(m);
    for (int i = 0; i < m; ++i) a[i] = Choose(n - 1, i);
    for (int i = 0; i < m; i += 2) b[i] = Choose(i / 2 + n - 2, n - 2);

    int sub = 0, y = 0;
    for (int i = m - 1, j = 0; i >= 0; --i) {
        while (j < m && i + j < m) (y += b[j++]) %= kMod;
        sub += 1LL * a[i] * y % kMod;
        if (sub >= kMod) sub -= kMod;
    }
    sub = 1LL * sub * n % kMod;
    printf("%d\n", (ans + kMod - sub) % kMod);
    return 0;
}


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

typedef long long int   ll;
#define cases           int t;cin>>t;while(t--)
#define FIO             ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define scan(n)         scanf("%d",&n)
#define pb              push_back
#define mod             1000000007
#define maxsz           200001
#define int             ll

using namespace std;

signed main(){
    string s,t;cin>>s>>t;
    if(s.size()!=t.size()-1){
        cout<<"No"<<endl;
    } else {
        t.pop_back();
        if(s!=t){
            cout<<"No"<<endl;
        } else{
            cout<<"Yes"<<endl;
        }
    }
}


Measured memory_bytes: 3628
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

template <typename QvQ> inline QvQ Min(QvQ a,QvQ b){if(a<b) return a;return b;}
template <typename QvQ> inline QvQ Max(QvQ a,QvQ b){if(a>b) return a;return b;}

#define inf 0x7f7f7f7f
#define dinf 0x3f3f3f3f

#define ll long long
#define rei register int
#define inv inline void

#define bl putchar(' ')
#define ed putchar('\n')

#define read2(a,b) read(a),read(b)
#define write2(a,b) write(a),bl,write(b)
#define read3(a,b,c) read(a),read(b),read(c)
#define write3(a,b,c) write(a),bl,write(b),bl,write(c)

template <typename QvQ>inv read(QvQ &x)
{
	x=0;int f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=x*f;
}
template <typename QvQ>inv write(QvQ x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+48);
}
using namespace std;
#define MAXN 10005
int n,a[MAXN],b[MAXN];
int main()
{
	read(n);
	for(rei i=1;i<n;++i) read(b[i]); b[n]=inf;
	a[1]=b[1]; int ans=a[1];
	for(rei i=2;i<=n;++i)
	{
		a[i]=Min(b[i],b[i-1]);
		ans+=a[i];
	}
	write(ans);
	return 0;
}

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

using namespace std;

int main(void) {
  string s;
  int n = 3;
  cin >> s;
  for (int i = 0; i < n; i++) {
    if (s[i] == '7') {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3628
//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//{akari : 1D, yukari : 2D, maki : 3D} vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//{akane : ascending order, aoi : decending order} priority queue
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Libraries ---------------------------------//

//------------------------------- Dubug Functions ---------------------------//

inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}

//------------------------------- Solver ------------------------------------//

void solve()
{
    i64 n;
    cin >> n;
    if (n & 1)
    {
        cout << 0 << endl;
        return;
    }
    n /= 2;
    i64 ans = 0;
    while (n)
    {
        ans += n / 5;
        n /= 5;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String args[]){
		new Main().mainrun();
	}

	private Scanner scan;
	private long n,money;


	private void mainrun() {
		scan = new Scanner(System.in);

		n = scan.nextInt();
		money = 100000;
		for(int i = 0;i < n;i++) {
			looprun();
		}

		System.out.println(money);

		scan.close();

	}

	private void looprun() {
		money += (long)(money * 0.05);

		if(money % 1000 != 0) {
			money += 1000 - money % 1000;
		}
	}
}


Measured memory_bytes: 26132
def solve():
    N, M  = map(int, input().split())
    Hs = list(map(int, input().split()))

    td = {}
    goodtd = {}
    for i in range(N):
        td[i+1] = Hs[i]
        goodtd[i+1] = 0


    for i in range(M):
        A, B = map(int, input().split())
        if td[A] < td[B]:
            if A in goodtd:
                del goodtd[A]
        elif td[B] < td[A]:
            if B in goodtd:
                del goodtd[B]
        elif td[B] == td[A]:
            if A in goodtd:
                del goodtd[A]
            if B in goodtd:
                del goodtd[B]
    
    print(len(goodtd))

solve()

Measured memory_bytes: 33096
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int N, D; cin >> N >> D;
    vector<vector<int>> X;
    rep (i, 0, N) {
        vector<int> x;
        rep (j, 0, D) {
            int in; cin >> in;
            x.push_back(in);
        }
        X.push_back(x);
    }

    int ans = 0;
    vector<double> ans_vec;
    rep (i, 0, N) {  // iで行単位のイテレーション
        rep (j, i+1, N) {  // jでi以降の行をイテレーション
            int tmp = 0;
            rep (k, 0, D) {  // 項数のイテレーション
                tmp += pow(abs(X[i][k] - X[j][k]), 2);
            }

            bool flag = false;
            rrep (k, 0, tmp) {
                if (pow(k, 2) == tmp) flag = true;
            }
            if (flag) ++ans;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
/*I know about "bits/stdc++.h" 
But I am not using it for some technical issue*/

#include "iostream"
#include "algorithm"
#include "iomanip"
#include "vector"
#include "set"
#include "sstream"
#include "fstream"
#include "cstring"
#include "cmath"
#include "utility"
#include "map"
#include "bitset"
#include "cassert"
#include "deque"

#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define obit __builtin_popcount
#define pof pop_front
#define mod (int)1e9+ 7
#define For(i,a,n) for(i=a;i<n;i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned short int us;
typedef short int ss;
typedef long double ld;
int dp[12][13];
int mn = mod;

bool check(int m,int x,set<int> tony){
	int ar[m],i,k;
	memset(ar,0,sizeof(ar));
	for(int node: tony){
		For(k,1,m+1) ar[k-1] += dp[node][k];
	}
	For(i,0,m){
		if(ar[i]<x) return 0;
	}
	return 1;
}
void recur(set<int> tony, int x,int node,int m,int n,int cc){
	if(check(m,x,tony)){
		mn = min(mn,cc);
		return;
	}
	if(node>= n) return;
	int i;
	recur(tony,x,node+1,m,n,cc);
	tony.insert(node);
	int cost = dp[node][0] + cc;
	recur(tony,x,node+1,m,n,cost);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m,x,j,i;
	cin>>n>>m>>x;
	For(i,0,n){
		For(j,0,m+1){
			cin>>dp[i][j];
		}
	}
	set<int> tony;
	recur(tony,x,0,m,n,0);
	if(mn == mod) cout<<-1;
	else cout<< mn;
	return 0;
}

Measured memory_bytes: 3668
/*input
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9
*/

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

const int INF = 1001001001;
int n, m, x;
vector<int> c;
vector<vector<int>> a;
vector<int> sum;

bool ok() {
  rep(i, m) if (sum[i] < x) return false;
  return true;
}

int dfs(int i=0, int co=0) {
  if (i == n) {
    if (ok()) {
      // printf("%d\n", co);
      return co;
    }
    else {
      // printf("%d\n", co);
      return INF;
    }
  }
  int n1, n2;
  n1 = dfs(i+1, co);
  rep(j, m) sum[j] += a[i][j];
  n2 = dfs(i+1, co+c[i]);
  int res = min(n1, n2);
  rep(j, m) sum[j] -= a[i][j];
  return res;
}

int main() {
  cin >> n >> m >> x;
  c.resize(n);
  a.resize(n, vector<int>(m));
  rep(i, n) {
    cin >> c[i];
    rep(j, m) cin >> a[i][j];
  }
  sum.resize(m, 0);
  int ans = dfs();
  if (ans == INF) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

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

int main()
{
  int N, K, h;
  cin >> N >> K;

  int ans = 0;

  for (int i = 0; i < N; i++)
  {
    cin >> h;
    if (h >= K)
      ans++;
  }

  cout << ans << endl;
}


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

#define all(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;

int main() {
    ll n; cin >> n;
    V<ll> a(n), b(n), c(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n; i++) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));

    ll sum = 0;
    for(int i = 0; i < n; i++){
        auto itea = lower_bound(all(a), b[i]);
        auto itec = upper_bound(all(c), b[i]);
        sum += (itea - a.begin()) * (c.end() - itec);
    }
    cout << sum << endl;

}


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

typedef long long ll;
typedef pair<int, int> pii;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()

#define endl "\n"

void use_cio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto x : V) os << x << ", ";
  return os << "]";
}

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

int main() {
  use_cio();
  int x,a;
  cin >> x >> a;
  cout << ( (x<a)?0:10)<<endl;
}


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

struct SCC{
  Int n;
  vector<vector<Int> > G,rG,T,C;
  vector<Int> vs,used,belong;
  SCC(){}
  SCC(Int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
  
  void add_edge(Int from,Int to){
    //cout<<from<<" "<<to<<endl;
    G[from].push_back(to);
    rG[to].push_back(from);
  }
  
  void input(Int m,Int offset=0){
    Int a,b;
    for(Int i=0;i<m;i++){
      cin>>a>>b;
      add_edge(a+offset,b+offset);
    }
  }
  
  void dfs(Int v){
    used[v]=1;
    for(Int i=0;i<(Int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
  
  void rdfs(Int v,Int k){
    used[v]=1;
    belong[v]=k;
    C[k].push_back(v);
    for(Int i=0;i<(Int)rG[v].size();i++){
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
  
  Int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(Int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
    fill(used.begin(),used.end(),0);
    Int k=0;
    for(Int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
	T.push_back(vector<Int>());
	C.push_back(vector<Int>());
	rdfs(vs[i],k++);
      }
    }
    for(Int i=0;i<n;i++)
      for(Int u:G[i])
	if(belong[i]!=belong[u])
	  T[belong[i]].push_back(belong[u]);
    for(Int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> x(n),y(n);
  for(Int i=0;i<n;i++) cin>>x[i]>>y[i];

  using T = tuple<Int,Int,Int>;
  vector<T> v;
  for(Int i=0;i<n;i++){
    v.emplace_back(x[i],0,i);
    v.emplace_back(y[i],1,i);
  }
  sort(v.begin(),v.end());
  
  Int m=1;
  while(m<(Int)v.size()) m*=2;
  //cout<<m<<endl;
  
  auto calc=[&](Int d){
    SCC scc(2*m-1+2*n);
    for(Int i=0;i<m-1;i++){
      scc.add_edge(i,i*2+1);
      scc.add_edge(i,i*2+2);
    }
    
    function<void(Int,Int,Int,Int,Int,Int)> dfs=
    [&](Int a,Int b,Int k,Int l,Int r,Int f){
      if(l>=r) return;
      if(r<=a||b<=l) return;
      if(a<=l&&r<=b){
	scc.add_edge(f,k);
	return;
      }
      Int mid=(l+r)>>1;
      dfs(a,b,k*2+1,l,mid,f);
      dfs(a,b,k*2+2,mid,r,f);
    };
    
    for(Int i=0;i<(Int)v.size();i++){
      Int z,t,p;
      tie(z,t,p)=v[i];
      Int idx=2*m-1+n*t+p,idy=2*m-1+n*(!t)+p;
      scc.add_edge(m-1+i,idy);
      Int a=lower_bound(v.begin(),v.end(),T(z-(d-1),-1,-1))-v.begin();
      Int b=lower_bound(v.begin(),v.end(),T(z+d,-1,-1))-v.begin();
      //cout<<a<<" "<<i<<" "<<b<<endl;
      dfs(a,i,0,0,m,idx);
      dfs(i+1,b,0,0,m,idx);
    }
    //cout<<"d="<<d<<endl;
    scc.build();
    for(Int i=0;i<n;i++)
      if(scc.belong[2*m-1+i]==scc.belong[2*m-1+n+i]) return 0;
    return 1;
  };
  
  Int l=0,r=1e12;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(calc(m)) l=m;
    else r=m;
  }
  cout<<l<<endl;
  return 0;
}
  


Measured memory_bytes: 30824
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n, m;

int read() {
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void Upd(int &x, int y) { x = (x + y) % mod; }
int mul(int x, int y) { return 1ll * x * y % mod; }
struct matx {
    int a[4][4];
    friend matx operator *(const matx& a, const matx& b) {
        matx c; memset(c.a, 0, sizeof(c.a));
        for(int i = 0; i < 3; i ++)
            for(int j = 0; j < 3; j ++)
                for(int k = 0; k < 3; k ++)
                    Upd(c.a[i][j], mul(a.a[i][k], b.a[k][j]));
        return c;
    }
}A, B, ans;

void init() {
    A.a[0][0] = 1, A.a[0][1] = 2, A.a[0][2] = 1;
    A.a[1][1] = 1, A.a[1][2] = 1;
    A.a[2][0] = 1, A.a[2][1] = 2, A.a[2][2] = 2;
    memcpy(B.a, A.a, sizeof(A.a)); 
    B.a[2][0] = B.a[2][1] = 0, B.a[2][2] = 1;
}

matx Qpow(matx x, int timer) {
    matx base; memset(base.a, 0, sizeof(base.a));
    for(int i = 0; i < 3; i ++) base.a[i][i] = 1;
    for(; timer; timer >>= 1, x = x * x)
        if(timer & 1) base = base * x;
    return base;
}

int main() {
    n = read(), m = read();
    init(); int last = 0;
    ans.a[0][0] = 1;
    for(int i = 1; i <= m; i ++) {
        int x = read();
        ans = ans * Qpow(A, x - last);
        ans = ans * B, last = x + 1; 
    }
    ans = ans * Qpow(A, n - last);
    printf("%d\n", ans.a[0][2]);
    return 0;
}

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

using namespace std;

int cnt[3];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < 3; ++i) {
    cnt[i] = 0;
  }
  const int mod = 1'000'000'007;
  long long ans = 1;
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    int ways = 0;
    for (int j = 0; j < 3; ++j) {
      if (cnt[j] == x) {
        ++ways;
      }
    }
    ans *= ways;
    ans %= mod;
    for (int j = 0; j < 3; ++j) {
      if (cnt[j] == x) {
        ++cnt[j];
        break;
      }
    }
  }
  printf("%d\n", (int)ans);
}


Measured memory_bytes: 256
#pragma region include
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstdio>
#include <tuple>
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (n); i < (m); i++)
#define MOD 1000000007
#define INF 1000000000
#define LLINF 4000000000000000000
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#pragma endregion

#define dump(x) cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl;
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    REP(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// map出力
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}

//UnionFind
class UnionFind {
private:
    vector<int> par;
public:
    UnionFind(int n) {
        par = vector<int>(n, -1);
    }

    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return false;
        if (size(rx) < size(ry)) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
        return true;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M; cin >> N >> M;
    vector<int> a(M), b(M);
    int ans = 0;
    REP(i, M) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    REP(i, M) {
        UnionFind uni(N);
        int cnt = N;
        REP(j, M) {
            if (i != j) {
                if (uni.unite(a[j], b[j])) {
                    cnt--;
                }
            }
        }
        if (cnt == 2) {
            ans++;
        }
    }
    cout << ans << endl;
    getchar(); getchar();
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  
  int a;
  
  scanf("%d",&a);
    
  a = a % 1000;
  
  if(a == 0){
    printf("%d",0);
  
  }else{
    printf("%d",1000 - a);
    
  }
  
  return 0;
}

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


int main() {

    int x, t;
    cin >> x >> t;
    cout << max(x - t, 0) << endl;
    return 0;
}

Measured memory_bytes: 256
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
A = [list(map(int,input().split())) for _ in range(H)]
dp = [float("INF")]*(10)
dp[1] = 0
cnt = 0
while cnt <= 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[j] = min(dp[j],dp[i]+C[j][i])

cost = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            cost += dp[A[i][j]]
print(cost)

Measured memory_bytes: 74192
#include<stdio.h>

int N;
int M;

int map[9][9];
int f[9];
int count=0;

void visit(int,int);

int main(void){
    scanf("%d%d",&N,&M);

    int a[M],b[M];

    int i,j;
    for(i=0;i<9;i++){
        f[i]=0;
    }

    for(i=0;i<9;i++){
        for(j=0;j<9;j++){
            map[i][j]=0;
        }
    }

    for(i=0;i<M;i++){
        scanf("%d%d",&a[i],&b[i]);
        map[a[i]][b[i]]=1;
        map[b[i]][a[i]]=1;
    }

    f[1]=1;
    visit(1,N);

    printf("%d",count);

    return 0;

}

void visit(int v,int N){
    int i;

    int sum_f=0;
    for(i=0;i<N+1;i++){
        sum_f+=f[i];
    }

    if(sum_f==N){
        count++;
        return;
    }
    
    for(i=1;i<N+1;i++){
       if(f[i]==0 && map[i][v]==1){
           f[i]=1;
           visit(i,N);
           f[i]=0;
       }
    }

    return;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int N;
int dp[10001];

int main(){
  dp[0]=1;
  cin>>N;
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    for(int j=10000;j>=0;j--){
      if(j-a>=0 && dp[j-a]==1)dp[j]=1;
    }
  }
  int ans=0;
  for(int i=0;i<=10000;i++){
    if(i%10>0&&i>ans&&dp[i])ans=i;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAXN 10005
using namespace std;
long long ans1,ans2,sumone;
int tem,n,a[MAXN],b[MAXN];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
       scanf("%d",&a[i]);
       ans1+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
       scanf("%d",&b[i]);
       ans2+=b[i];
    }
    if(ans1>ans2)
    {
        printf("No\n");
        return 0;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]==b[i])
            {
                continue;
            }
            //单调的时候有一种保证最优的手段:积累1
            if(a[i]<b[i])
            {
                if((a[i]&1)&&(b[i]&1))
                {
                    sumone+=(b[i]-a[i])/2;
                }
                if((!(a[i]&1))&&(!(b[i]&1)))
                {
                    sumone+=(b[i]-a[i])/2;
                }
                if((a[i]&1)&&(!(b[i]&1)))
                {
                    sumone+=(b[i]+1-(a[i]+2))/2;
                }
                if((!(a[i]&1))&&(b[i]&1))
                {
                    sumone+=(b[i]+1-(a[i]+2))/2;
                }
                continue;
            }
            if(a[i]>b[i])
            {
                sumone-=a[i]-b[i];
            }
               // printf("%d\n",sumone);
        }
        if(sumone<0)
        {
            printf("No\n");
            return 0;
        }
            printf("Yes\n");
    }
}


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v)                                                            \
  do {                                                                         \
    x = max(x, v);                                                             \
  } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll a,b,k;
  cin>>a>>b>>k;
  ll ans1 = max((ll)0, a-k);
  ll ans2 = max((ll)0, b-(k-(a-ans1)));
  cout << ans1 << " " << ans2 << endl;
  return 0;
}


Measured memory_bytes: 256