akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
int K;
int X[100];
int main(){
  int i, res=0;
  rd(N);
  rd(K);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
    }
  }
  for(i=0;i<(N);i++){
    res +=min_L(X[i], K-X[i]);
  }
  wt_L(2*res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// int N, K, X[100];
// {
//   int i, res = 0;
//   rd(N, K, X(N));
//   rep(i,N) res += min(X[i], K-X[i]);
//   wt(2res);
// }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,c,k;cin>>a>>b>>c>>k;
    ll ans = 0;

    if(a>=k) ans = k;
    else if(a+b >= k) ans = a;
    else ans = a-(k-a-b);
    cout<<ans<<endl;

}

Measured memory_bytes: 3620
#include<iostream>
#include<set>
#include<vector>
#define N 100000
using namespace std;
set<int> squares;
vector<int> pts[N+1];
int main()
{
	int n, d; cin >> n >> d;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < d; j++)
		{
			int x; cin >> x;
			pts[i].push_back(x);
		}
	
	for(int n = 0; n <= 30000; n++)
		squares.insert(n*n);
		
	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = i+1; j < n; j++)
		{
			int dist2 = 0;
			for(int k = 0; k < d; k++)
				dist2 += (pts[i][k]-pts[j][k])*(pts[i][k]-pts[j][k]);
			ans += squares.count(dist2);
		}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3968
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

cnt = [0]*65

for e in a:
    for i in range(65):
        if (e>>i)&1 == 1:
            cnt[i] += 1

res = 0
p = 1

for e in cnt:
    res = (res+p*e*(n-e)%mod)%mod
    p = p*2%mod

print(res)


Measured memory_bytes: 123132
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <limits>
#include <set>
#include <stack>
#include <queue>
#include <list>
#include <cmath>

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(), a.end());

    double ans = a[0];
    rep(i, n-1) {
        ans += a[i+1];
        ans /= 2;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>//
#include <vector>//
#include <map>
#include <cstdlib>
#include <numeric>
#include <algorithm>//ソート等に使用
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <thread>///////////////////
#include <queue>//幅優先等のキュー

#define rep(i,m,n) for(int i=(m);i<(n);i++)
#define rem(i,m,n) for(int i=(m);i>(n);--i)

#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long int;
using ld = long double;
using std::swap;

vector<int> v;
vector<int> w;
vector<long long int> vll;
vector<long long int> wll;
//vector<vector<int>> vec(50, vector<int>(4, 0));
vector<vector<int>> vv;
vector<vector<int>> ww;


int main() {
	int N;
	cin >> N;
	v.resize(N);
	w.resize(N);
	rep(i, 0, N) {
		cin >> v[i] >> w[i];
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	if (N % 2 == 0) {
		ld w_mid, v_mid;
		w_mid = (w[N / 2] + w[(N / 2) - 1]) / 2. ;
		v_mid = (v[N / 2] + v[(N / 2) - 1]) / 2. ;
		
		cout << (int)(w_mid / 0.5 - v_mid / 0.5 + 1) << '\n';
	}
	else {
		cout << w[N / 2] - v[N / 2] + 1 << '\n';
	}

	return 0;

}

Measured memory_bytes: 4780
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,ma1,ans=0;
    cin>>n;
    int a[n],b[n],c[n];
    int ma[3][n];
    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }
    if(n==1)
    {
       ma1=max(a[0],b[0]);
       ma1=max(ma1,c[0]);
       cout<<ma1; return 0;
    }
    ma[0][0]=a[0];ma[1][0]=b[0];ma[2][0]=c[0];
    for(i=1;i<n;i++)
    {
        ma[0][i]=max(ma[1][i-1],ma[2][i-1])+a[i];
        ma[1][i]=max(ma[2][i-1],ma[0][i-1])+b[i];
        ma[2][i]=max(ma[1][i-1],ma[0][i-1])+c[i];

    }
    ans=max(ma[0][n-1],ma[1][n-1]);
    ans=max(ans,ma[2][n-1]);
    cout<<ans;
}

Measured memory_bytes: 2560
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
nums = getList()
ans = 0
for i, num in enumerate(nums):
    for j, num2 in enumerate(nums[i+1:]):
        ans += num * num2


print(ans)

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int>> vvint;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<int, vector<int>, greater<int>> spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int>> bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;        //大きい順に取り出し

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)

int INF = 1e9;
int NIL = -1;
ll MOD = 1000000007;
ll LINF = 1e18;
double EPS = 1e-9;
double PI = M_PI;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}
//-----------------------------------------

//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::chrono::system_clock::time_point start,end;
    start = std::chrono::system_clock::now();
    int n ;
    ll x ;
    cin >> n >>  x ;
    vll a(n+1,0) ;
    REP(i,n){
        cin >> a[i+1] ;
    }
    ll ans = 0 ;
    FOR(i,1,n+1){
        ll tmp = max((a[i]+a[i-1]-x),(ll)0) ;
        ans += tmp ;
        a[i] -= tmp ;
    }
    cout << ans <<endl;



    end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(end - start).count();
    //std::cout << elapsed <<"ms"<< std::endl;

    

    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
//#define int long long int
const int lim = (int)1e5 + 2;
vi adj[lim];
vi start(lim);
vi len(lim, -1);
inline pii intersect(int i, int j){
   if(len[i] == -1 && len[j] == -1)return mp(0, -1);
   if(len[i] == -1)return mp(start[j], len[j]);
   if(len[j] == -1)return mp(start[i], len[i]);
   if(start[i] % 2 != start[j] % 2)return mp(0, 0);
   int s = max(start[i],start[j]);
   int e = min(start[i] + len[i]*2 - 2, start[j] + len[j]*2 -2);
   if(e < s)return mp(0, 0);
   return mp(s, (e- s)/2 + 1);
}
inline void calc(int i, int k){
    //need to adjust the range for the child
    if(len[i] != -1)start[i]--,len[i]++;
    pii temp = intersect(i, k);
    if(len[i] != -1)start[i]++,len[i]--;
    start[k] = temp.first;
    len[k] = temp.second;
}
bool check(int cur, int P){
    for(int child: adj[cur]){
        if(child != P){
            if(check(child, cur))return true;
            calc(child, cur);
        }
    } 
//    cout << cur << " " << start[cur] << " " << len[cur]  <<endl;
    if(len[cur] == 0)return true;
    return false;
}
void dfs(int cur, int P){
    if(P != -1){
        int pval = start[P];
        if(len[cur] == -1)start[cur] = pval + 1;
        else{
            if(start[cur] < pval)start[cur] = pval -1;
            else start[cur] = pval+1;
        }
        len[cur] = 1;
    }
    for(int child: adj[cur]){
        if(child != P){
            dfs(child, cur);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    int n;cin >> n;
    int x, y;
    FOR(i, n -1){
        cin >>x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    int k;cin >> k;
    FOR(i, k){
        cin >>x >> y;
        start[x] = y;
        len[x] = 1;
    }
    if(check(1, -1))cout << "No";
    else{
        cout << "Yes" << "\n";
        //assuming start[1] = 0 if not set otherwise the set value will be used
        len[1] = 1;
        dfs(1, -1);
        FOR1(i, n){
            cout << start[i] << "\n";
        }
    }
}




Measured memory_bytes: 14976
n, m = [int(i) for i in input().split()]
s = []
c = []

start = 10 ** (n - 1)
end = 10 ** n
if n == 1:
    start = 0

for i in range(m):
    tmp = [int(j) for j in input().split()]
    s.append(tmp[0])
    c.append(tmp[1])

for i in range(start, end):
    status = True
    for j in range(m):
        if(str(i)[s[j] - 1] != str(c[j])):
            status = False
    if(status):
        print(i)
        exit()
print(-1)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pl;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
#define SHOW(x) cout << #x << ": " << x << endl;
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){   
    int h,n;
    cin>>h>>n;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    int sum = 0;
    rep(i,n)sum += a[i];
    if(sum >= h)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 640
D, G = [int(i) for i in input().split()]
P = []
C = []
for i in range(D):
    p, c = input().split()
    P.append(int(p))
    C.append(int(c))

res = 1000
for i in range(1 << D):
    b = format(i, '01000b')[::-1]
    s = 0
    cnt = 0
    k = 0
    for j in range(D):
        if b[j] == '1':
            s += 100 * (j + 1) * P[j] + C[j]
            cnt += P[j]
        else:
            k = j
    if s >= G:
        res = min(res, cnt)
    else:
        for l in range(P[k] - 1):
            s += 100 * (k + 1)
            cnt += 1
            if s >= G:
                res = min(res, cnt)
                break
print(res)


Measured memory_bytes: 9168
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision(15) << << endl;
#include <cassert>
#include <limits>
//#include "atcoder/all"

using namespace std;
//using namespace atcoder;

#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
//#define P pair<int,int>

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};


int main(){
    string s,t; cin >> s >> t;
    int sz = s.size(),tz = t.size();

    if(sz < tz){cout << "UNRESTORABLE" << endl; return 0;}
    int i;
    bool ok = false;
    for(i = sz-1; i >= 0; --i){
        int k = tz-1;
        while(k >= 0){
            int a = i-(tz-1-k);
            if(a<0) break;
            if(s[a] == '?' || s[a] == t[k]) {
                k--;
                if(k==-1) {ok = true; break;}
            }else break;
        }
        if(ok) {
            rep(j,i-tz+1){
                if(s[j] == '?') s[j] = 'a';
            }
            for(int j = i+1; j < sz; j++) if(s[j] == '?') s[j] = 'a';
            break;
        }
    }
    if(ok) {
        rep(j, i-tz+1) cout << s[j];
        cout << t;
        for(int j = i+1; j < sz; ++j) cout << s[j];
    }else cout << "UNRESTORABLE" << endl;
}



Measured memory_bytes: 3620
#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, q, inf=2e9, cnt;
vector<int> par ;
vector<pair<int,pair<int,int> > > v;
map<int,int> id ;
int tree[3000006];
void update(int node, int s, int e, int l, int r, int val)
{
    if(s>r||e<l)
        return ;
    if(s>=l && e<=r)
    {
        tree[node]=min(tree[node],val);
        return ;
    }
    int m=(s+e)/2;
    update(2*node,s,m,l,r,val);
    update(2*node+1,m+1,e,l,r,val);
}
int solve(int node, int s,int e, int pos)
{
    if(s==e)
        return tree[node];
    int m=(s+e)/2;
    tree[2*node]=min(tree[node],tree[2*node]);
    tree[2*node+1]=min(tree[node],tree[2*node+1]);
    return pos<=m ? solve(2*node,s,m,pos) : solve(2*node+1,m+1,e,pos);
}
int main()
{
    IO
    cin>>n>>q;
    for(int i=1; i<=3e6; i++)
        tree[i]=inf;
    for(int i=1; i<=n; i++)
    {
        int s, t, x;
        cin>>s>>t>>x;
        v.push_back({x,{s-x,t-x-1}});
        id[s-x]++;
        id[t-x-1]++;
    }
    for(int i=1; i<=q; i++)
    {
        int d;
        cin>>d;
        id[d]++;
        par.push_back(d);
    }
    for(auto i : id)
        id[i.first]=++cnt;
    for(int i=0; i<n; i++)
    {
        int l=id[v[i].second.first], r=id[v[i].second.second];
        update(1,1,cnt,l,r,v[i].first);
    }
    for(int i=0; i<q; i++)
    {
        int ans=solve(1,1,cnt,id[par[i]]);
        if(ans==inf)
            ans=-1;
        cout<<ans<<"\n";
    }
}


Measured memory_bytes: 46216
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int N, M;
    cin >> N >> M;

    priority_queue<int> que;
    for(int i=0; i<N; i++){
        int A;
        cin >> A;
        que.push(A);
    }
    for(int i=0; i<M; i++){
        int tmp=que.top();
        que.pop();
        tmp/=2;

        que.push(tmp);
    }
    long long ans=0;
    for(int i=0; i<N; i++){
        ans+=(long long) que.top();
        que.pop();
    }
    cout << ans << endl;

}

Measured memory_bytes: 892
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> P;

#define INF 1145141919810

struct edge {
    int to, cost;
};

vector<edge> G[100010];
long long d[100010];

int main() {
    int v, e, r;
    scanf("%d", &v);
    scanf("%d", &e);
    scanf("%d", &r);
    for (int i = 0; i < e; i++) {
        int s, t, d;
        scanf("%d", &s);
        scanf("%d", &t);
        scanf("%d", &d);
        edge e;
        e.to = t;
        e.cost = d;
        G[s].push_back(e);
    }
    fill(d, d + v, INF);
    d[r] = 0;

    priority_queue<P, vector<P>, greater<P> > q;

    q.push(P(0, r));

    while (!q.empty()) {
        P p = q.top();
        q.pop();
        int v = p.second;
        if (d[v] < p.first) { continue; }
        for (int i = 0, size = G[v].size(); i < size; i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(P(d[e.to], e.to));
            }
        }
    }

    for (int i = 0; i < v; i++) {
        if (d[i] == INF) {
            printf("INF\n");
        } else {
            printf("%lld\n", d[i]);
        }
    }
}

Measured memory_bytes: 13000
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int segtree[262144];
void add(int a,int b,int c,int d,int e,int val){
	if(d<a||b<c);
	else if(c<=a&&b<=d){
		segtree[e]+=val;
	}
	else{
		add(a,(a+b)/2,c,d,e*2,val);
		add((a+b)/2+1,b,c,d,e*2+1,val);
	}
	if(e>1){
		int v=max(segtree[e],segtree[e^1]);
		if(v>0){
			segtree[e/2]+=v;
			segtree[e]-=v;
			segtree[e^1]-=v;
		}
	}
}
int query(int a,int b,int c,int d,int e,int now){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d)return now+segtree[e];
	else {
		return max(query(a,(a+b)/2,c,d,e*2,now+segtree[e]),query((a+b)/2+1,b,c,d,e*2+1,now+segtree[e]));
	}
}
int d[100000];
int h[100000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	a--;
	for(int i=0;i<a;i++)scanf("%d%d",d+i,h+i);
	priority_queue<pair<int,int> > Q;
	long long ret=0;
	int now=b;
	for(int i=0;i<a;i++){
		add(0,131071,i,i,1,now);
		now-=d[i];
		Q.push(make_pair(h[i],i));
	//	printf("%d\n",now);
		while(now<=0){
			int cost=Q.top().first;
			int at=Q.top().second;
			Q.pop();
			int q=query(0,131071,at,i,1,0);
		//	printf("%d\n",q);
			if(cost+q>b){
				Q.push(make_pair(b-q,at));
				continue;
			}
			int usemax=min((-now)/cost+1,(b-q)/cost);
			ret+=usemax;
			now+=usemax*cost;
	//		printf("%d %d %d\n",cost,at,usemax);
			add(0,131071,at,i,1,usemax*cost);
			Q.push(make_pair(cost,at));
		}
	//	printf("%d\n\n",now);
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn= 5e5+5;
#define mod 1000000007
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main() {
    int n,m,c;
    cin>>n>>m>>c;
    int cnt=0;
    int arr[m];
    for(int i=0;i<m;i++)cin>>arr[i];
    for(int i=0;i<n;i++){
        int temp=0;
        for(int i=0;i<m;i++){
            int x;
            cin>>x;
            temp+=arr[i]*x;
        }
        if(temp+c>0)cnt++;
    }
    cout<<cnt;
}



Measured memory_bytes: 3632
def main():
    s = str(input())

    max = 0
    count = 0
    for c in s:
        if c == "R":
            count += 1
        else:
            if max < count:
                max = count
                count = 0
    
    if max < count:
        max = count

    print(str(max))

if __name__ == "__main__":
    main()

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

using namespace std;

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

    vector<int> a(n), b(n), c(n);

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

    int dp[n+1][3];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 3; j++){
            dp[i][j] = INT_MIN;
        }
    }
    for(int i = 0; i < 3; i++) dp[0][i] = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            if(j == 0) dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + a[i-1];
            if(j == 1) dp[i][j] = max(dp[i-1][0], dp[i-1][2]) + b[i-1];
            if(j == 2) dp[i][j] = max(dp[i-1][1], dp[i-1][0]) + c[i-1];
        }
    }

    cout << max(dp[n][0], max(dp[n][1], dp[n][2]));
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

int n,k;
map<int,int> mp;
priority_queue<int,vector<int>,greater<int> > pq;

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

	cin>>n>>k;
	REP(i,n) {
		int a;cin>>a;
		mp[a]++;
	}
	for(auto x:mp) pq.push(x.se);

	int sum=0;
	while(pq.size()>k) {
		sum+=pq.top();
		pq.pop();
	}
	cout<<sum<<endl;

	return 0;
}


Measured memory_bytes: 10744
#include <bits/stdc++.h>
    #define Mod 1000000007
    #define INF 1e9
    #define INFL 9e18
    #define EPS 1e-9
    #define pb push_back
    #define mp make_pair
    #define SET(a) memset(a,-1,sizeof(a))
    #define CLR(a) memset(a,0,sizeof(a))
    #define CPY(a,b) memcpy(a,b,sizeof(a))
    #define all(a) (a).begin(),(a).end()
    #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define N 200005
    #define fs first
    #define sc second
    using namespace std;

    typedef  long long int ll;
    typedef pair<ll,ll> ii;
    typedef vector <ii> vii;
    typedef vector <ll> vi;
   
  

   
    int main()
    {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    ios;
    vii v;
    ll n,h,a,b;
 cin>>n>>h;
 for(int i=0;i<n;i++)
 {
  cin>>a>>b;
  v.pb(ii(a,1));
  v.pb(ii(b,0));
 }
sort(v.rbegin(),v.rend());
// for(int i=0;i<v.size();i++)
//   cout<<v[i].fs<<" "<<v[i].sc<<endl;
ll ans=0;
for(int i=0;i<v.size();i++)
{
  ll pp=v[i].fs;
  ll qq=v[i].sc;
  if(qq==0)
    ans++,h-=pp;
  else
  {
    ans+=ceil(double(h)/pp);
    break;
  }
  if(h<=0)
    break;
}
cout<<ans<<endl;

    return 0;


    }

Measured memory_bytes: 6524
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX 10000

using namespace std;
typedef long long ll;

 int main(){

  long long n,d;
   cin>>n>>d;

   int ans = (n+d*2+1 - 1)/(2*d+1);

   cout<<ans<<endl;

  return 0;
 }


Measured memory_bytes: 3596
H,W,M = list(map(int,input().split()))
B = []
for i in range(M):
    B.append(list(map(int,input().split())))

import heapq  # heapqライブラリのimport
Hs = [0]*(H+1)
Ws = [0]*(W+1)
HW = {}
for i in range(M):
    X,Y = B[i][0],B[i][1]
    Hs[X]+=1
    Ws[Y]+=1
    HW[str(X)+"_"+str(Y)] = 1

HM = max(Hs)
HMs = []
WM = max(Ws)
WMs = []
for i in range(H+1):
    if Hs[i]==HM:
        HMs.append(i)
for i in range(W+1):
    if Ws[i]==WM:
        WMs.append(i)
NHMs = len(HMs)
NWMs = len(WMs)

if NHMs*NWMs>M:
    print(HM+WM)
else:
    out = 0
    for i in range(NHMs):
        for j in range(NWMs):
            X,Y = HMs[i],WMs[j]
            if HW.get(str(X)+"_"+str(Y))!=1:
                out = 1
            else:
                continue
    print(out+HM+WM-1)

Measured memory_bytes: 223244
# -*- coding: utf-8 -*-

N, T = map(int, input().split())
ct = [None] * N
for i in range(N):
    c, t = map(int, input().split())
    ct[i] = c, t

c_filtered = [c for (c, t) in ct if t <= T]

if c_filtered:
    ans = min(c_filtered)
else:
    ans = "TLE"

print(ans)


Measured memory_bytes: 3060
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 31;
// clang-format on

int main(void)
{
  int N, i;
  cin >> N >> i;

  cout << N - i + 1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
typedef long long ll;

int main() {
  cout << fixed << setprecision(10);
  double l;
  cin >> l;
  double v = (l/3)*(l/3)*(l/3);
  cout  << v << endl; 
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#define maxn 100010
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
   if(x<=1)return false;
   for(int i=2;i<=int(sqrt(x));i++){
	   if(x%i==0)return false;
   }return true;
}
bool cmp(ll a,ll b){return a>b;}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll read() {
	char c = getchar(); ll w = 1; ll x = 0;
	while (!isdigit(c))
		(c == '-') && (w = -w), c = getchar();
	while (isdigit(c))
		x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
	x *= w;
}
void fl(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
		  dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int n, m;
 
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	cin >> n >> m;
	int cnt = 0;
	while (n)
	{
		++cnt;
		n /= m;
	}
	cout << cnt << endl;
	return 0;
}




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

using namespace std;

typedef long long LL;

const int N = 1010;

int n, k;

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

    int now = 1;
    while(n--)
    {
        if(now > k) now += k;
        else now *= 2;
    }

    cout << now << endl;
    return 0;
}


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

namespace bla
{
    class Program
    {
        static void Main()
        {
            string[] s = Console.ReadLine().Split();
            int d = int.Parse(s[0]);
            int g = int.Parse(s[1]) / 100;

            List<int> p = new List<int>();
            List<int> c = new List<int>();
            for (int i = 0; i < d; i++)
            {
                s = Console.ReadLine().Split();
                p.Add(int.Parse(s[0]));
                c.Add(int.Parse(s[1]) / 100);
            }
            while(p.Count < 10)
            {
                p.Add(0);
                c.Add(0);
            }

            int best = int.MaxValue;
            for (int i = 0; i < (1 << 10); i++)
            {
                int sum = 0;
                int count = 0;
                for (int j = 0; j < 10; j++)
                {
                    if ((i & (1 << j)) != 0)
                    {
                        sum += p[j] * (j+1) + c[j];
                        count += p[j];
                    }
                }
                if (sum < g)
                    continue;
                best = Math.Min(best, count);
                for (int j = 0; j < 10; j++)
                {
                    if ((i & (1 << j)) == 0)
                        continue;
                    int nsum = sum;
                    int ncount = count;
                    nsum -= c[j];
                    int r = 0;
                    while(nsum >= g && r <= p[j])
                    {
                        nsum -= j+1;
                        ncount--;
                        r++;
                    }
                    nsum += j + 1;
                    ncount++;
                    if(nsum >= g)
                        best = Math.Min(best, ncount);
                }
            }
            Console.WriteLine(best);
        }
    }
}

Measured memory_bytes: 13140
n = int(input())
a = list(map(int ,input().split()))

new_a = [a[0]]

now = a[0]
for i in range(1, n):
  if(now != a[i]):
    new_a.append(a[i])
    now = a[i]
    
n = len(new_a)

if(n == 1):
  print(1000)
  exit()

top = ["" for _ in range(n)]
if(new_a[0] < new_a[1]):
  top[0] = "l"
  top[1] = "h"
else:
  top[0] = "h"
  top[1] = "l"
  
for i in range(1, n):
  if(new_a[i-1] < new_a[i]):
    if(top[i-1] == "l"):
      top[i] = "h"
    else:
      top[i-1] = "n"
      top[i] = "h"
  else:
    if(top[i-1] == "l"):
      top[i-1] = "n"
      top[i] = "l"
    else:
      top[i] = "l"

mony = 1000
kabu = 0
for i in range(n):
  if(top[i] == "l"):
    if(i == n-1):
      break
    kabu_now = mony//new_a[i]
    mony -= new_a[i]*kabu_now
    kabu += kabu_now
    #print("get", kabu_now)
  elif(top[i] == "h"):
    kabu_now = kabu
    mony += kabu_now*new_a[i]
    kabu -= kabu_now
    #print("bye", kabu_now)
print(mony)

Measured memory_bytes: 9104
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int dist[100010],dist2[100010];
vector<int> g[100010];
void dfs(int now,int par,int d){
	dist[now]=d;
	for(int i=0;i<g[now].size();i++){
		if(g[now][i]!=par){
			dfs(g[now][i],now,d+1);
		}
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a); 
	}
	dfs(n,0,0);
	for(int i=0;i<100010;i++)dist2[i]=dist[i];
	dfs(1,0,0);
	int fec=0,snk=0;
	for(int i=1;i<=n;i++){
		if(dist2[i]>=dist[i])fec++;
		else snk++;
	}
	if(fec>snk)cout<<"Fennec"<<endl;
	else cout<<"Snuke"<<endl;
	return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define pob pop_back
#define mp make_pair
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230781640628
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll, ll> pll;
const ll M=1e9+7;
ll inf=1e18;
int main()
{
    int k;
    string s;
    cin>>k>>s;
    if(k>=s.length())
        cout<<s;
    else{
        for(int i=0;i<k;i++)
            cout<<s[i];
        cout<<"...";
    }
}


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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a,b,c;
    cin >>a>>b>>c;
    if (a+b+c>21){
        cout<<"bust";
    }
    else{
        cout<<"win";
    }

    
    return 0;
    
}


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

template<class T> ostream& operator<<(ostream &os, vector<T> V) {
    os << "[ ";
    for(auto v : V) os << v << " ";
    return os << "]";
}
template<class T> ostream& operator<<(ostream &os, set<T> S){
    os << "{ ";
    for(auto s:S) os<<s<<" ";
    return os<<"}";
}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
    os << "{ ";
    for(auto m:M) os<<"("<<m.F<<":"<<m.S<<") ";
    return os<<"}";
}

#define cerr cout

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

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
// erase,insert same as normal set

#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define all(v) (v).begin(),(v).end()
#define For(i,n) for(int i=0;i<(int)n;++i)
#define Rev(i,n) for(int i=(int)n-1;i>=0;--i)
#define Rep(i,n) for(int i=1;i<=(int)n;++i)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MP make_pair
#define d0(x) cout<<(x)<<" "
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl

const int maxn=1e6+100;
// // int mod=1e9+7;
// inline int mul(int a,int b){return (a*1ll*b)%mod;}
// inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
// inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
// inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
// inline int inv(int a){return power(a,mod-2);}
// inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 

ll t[maxn];
int main(){
	fio; cout<<fixed<<setprecision(25);
	#ifndef ONLINE_JUDGE 
		freopen("error.txt","w",stderr);
	#endif 
	ll n,T;
	cin>>n>>T;
	ll tot=0,tf=0,ts=0;
	Rep(i,n) cin>>t[i];
	Rep(i,n){
		if (t[i]<=tf){
			tot+=t[i]-ts;
		}
		else{
			tot+=tf-ts;
		}
		ts=t[i];
		tf=ts+T;
	}
	tot+=tf-ts;
	d1(tot);
}

Measured memory_bytes: 1792
N, M = map(int, input().split())

KS = []
for _ in range(M):
    ks = list(map(int, input().split()))
    KS.append(tuple([ks[0], set(ks[1:])]))

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

cnt = 0
for n in range(2**N):
    on_switchs = set()
    n_tmp = n
    for i in range(0, N):
        if n_tmp == 0:
            break
        else:
            if n_tmp % 2 == 1:
                on_switchs.add(N-i)
            n_tmp //= 2
    
    for m in range(M):
        if (len(on_switchs & KS[m][1]) % 2) != P[m]:
            break
    else:
        cnt += 1
            
print(cnt)

Measured memory_bytes: 3064
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);




	public static void main(String[] args) throws Exception {

		//setOut();
		int n = sc.nextInt();
		Long res=(long) 1;
		Long odd=(long)1;
		for (int i = 1; i <= n; i++) {
			int k=sc.nextInt();
			res*=3;
			if(k%2==0)
				odd*=2;
	
		}
		System.out.println(res-odd);

	}


}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n;
      cin>>n;
      vector<int> arr;
      vector<int> data(n+1,0);
      data[0]=3;
      for(int i=0;i<n;i++){
            int x;
            cin>>x;
            arr.pb(x);
      }
      int ans=1;
      for(int i=0;i<n;i++){
            ans=ans*data[arr[i]]%modulo;
            data[arr[i]]--;
            data[arr[i]+1]++;
      }
      cout<<ans;
}


Measured memory_bytes: 2168
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=1e9+7,MAX=1e5+1;
int n;
ll s;
set<pair<ll,ll>>adj[MAX];
vector<int>vis(MAX);
priority_queue<pair<ll,pair<ll,ll>>>st;
ll x;
ll dfs(int node){
    vis[node]=1;
    ll ret=0;
    for(auto i:adj[node]){
        if(!vis[i.first]){
            x=dfs(i.F);
            st.push({x*i.S,{i.S,x}});
            ret+=x;
        }
    }
    if(sz(adj[node])==1)
        ret++;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n;
    cin>>n;
    vector<int>res(n+1);
    lp(x, 1, 201) {
        lp(y, 1, 201) {
            lp(z,1,201){
                int q=x*x+y*y+z*z+x*z+x*y+y*z;
                if(q<=n)
                    res[q]++;
            }
        }
    }
    lp(i,1,n+1)
        cout<<res[i]<<endl;

}

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

int main ()
{
    int a,b,c;
    int ans=0;
    cin>>a>>b>>c;
    for(int i=a;i<=b;i++)
        if(i%c==0) ans++;
    cout<<ans<<endl;
	return 0;
}


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

// Combination Table
ll C[51][51]; // C[n][k] -> nCk

void comb_table(int N){
	for(int i=0;i<=N;++i){
		for(int j=0;j<=i;++j){
			if(j==0 or j==i){
				C[i][j]=1LL;
			}else{
				C[i][j]=(C[i-1][j-1]+C[i-1][j]);
			}
		}
	}
}

int main(void){
	int N,A,B;
	cin >>  N >> A >> B;

	const int NMAX=50;
	ll v[NMAX];

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

	comb_table(N);
	sort(v,v+N);
	reverse(v,v+N);
 
	R max_average=0.0;
	for(int i=0;i<A;++i){
		max_average+=v[i];
	}
	max_average/=A;

	int a_th_val_num=0,a_th_val_pos=0;
	for(int i=0;i<N;++i){
		if(v[i]==v[A-1]){
			a_th_val_num++;
			if(i<A){
				a_th_val_pos++;
			}
		}
	}

	ll cnt=0LL;
	if(a_th_val_pos==A){
		for(a_th_val_pos=A;a_th_val_pos<=B;++a_th_val_pos){
			cnt+=C[a_th_val_num][a_th_val_pos];
		}
	}else{
		cnt+=C[a_th_val_num][a_th_val_pos];
	}

	cout.precision(20);
	cout << fixed << max_average << endl;
	cout << cnt << endl;

	return 0;
}


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

int main() {
    ll N;
    cin >>N;
    ll mn =N-1;
    for(ll i=1;i<=sqrt(N);i++){
        if(N%i==0){
            mn =min(mn,N/i+i-2);
        }
    }
    cout << mn <<endl;
}

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

const int INF = 1000000;

struct Tool {int a, e, r;};
// bool operator<(const Tool& lhs, const Tool& rhs) {return lhs.r < rhs.r;}
bool operator<(const Tool& lhs, const Tool& rhs) {
  if(lhs.r != rhs.r) return lhs.r < rhs.r;
  return lhs.e < rhs.e;
}

int solve(int D, vector<Tool> tool) {
  sort(begin(tool), end(tool));
  vector<vector<int>> dp(D + 1, vector<int>(101, INF));
  dp[D][0] = 0;
  for(const auto& t: tool) {
    for(int hp = D; 0 <= hp; --hp) {
      for(int exp = 0; exp <= 100; ++exp) {
        if(exp < t.r) continue;
        int next_hp = max(0, hp - t.a);
        int next_exp = min(100, exp + t.e);
        dp[next_hp][next_exp] = min(dp[next_hp][next_exp], dp[hp][exp] + 1);
      }
    }
  }

  int result = INF;
  for(const auto& i: dp[0]) result = min(result, i);
  return result;
}

int main() {
  int D, N;
  while(cin >> D >> N, D | N) {
    vector<Tool> tool(N);
    for(auto& t: tool) cin >> t.a >> t.e >> t.r;

    int answer = solve(D, tool);
    if(answer == INF) cout << "NA" << endl;
    else              cout << answer << endl;
  }
}

Measured memory_bytes: 1260
#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>;


int main() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    rep(i,10) rep(j,10) rep(k,10) {
        for (int l = 0; l < N; ++l) {
            if (S.at(l) == '0' + i) {
                ++l;
                for (; l < N; ++l) {
                    if (S.at(l) == '0' + j) {
                        ++l;
                        for (; l < N; ++l) {
                            if (S.at(l) == '0' + k) {
                                ++ans;
                                l = N;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    vector<int> v(3);
    cin >> v[0] >> v[1] >> v[2];
    sort(begin(v), end(v));
    int ans = (v[1] - v[0]) + (v[2] - v[1]);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	const int sz = 200010;
	int n; cin >> n;
	int cnt = 0;
	int memo = 0;
	int a[n+1];
	int b[n+1];
	fill_n(a, n+1, 0);
	b[0] = 0;
	for( int i = 1; i <= n; ++i ) cin >> b[i];
	for( int i = n; i >= 1; --i ){
		int sum = 0;
		for( int k = i; k <= n; k += i ) sum += a[k];
		if( sum % 2 != b[i] ){
			if( cnt == 0 ) memo = i;
			++cnt;
			a[i] = 1;		
		}
	}
	cout << cnt << endl;
	for( int i = 1; i <= n; ++i ){
		if( a[i] == 1 ){
			cout << i;
			if( i != memo ) cout << ' ';
		}
	}
	if( cnt > 0 ) cout << endl;
	return 0;
}

Measured memory_bytes: 2432
N, M = map(int, raw_input().split())
E = [map(lambda v: int(v)-1, raw_input().split()) for i in range(M)]
ans = 0
for k in range(M):
    used = [False] * N
    used[0] = True
    que = [0]
    while que != []:
        s = que.pop(0)
        for i in range(M):
            if i != k:
                a, b = E[i]
                if (s == a) and not used[b]:
                    used[b] = True
                    que.append(b)
                elif (s == b) and not used[a]:
                    used[a] = True
                    que.append(a)
    ans += sum(used) < N
print ans

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

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

int N, M;
vector<pii> adj[100010];
int vis[100010];
ll dist[100010];

void dfs(int u) {
    vis[u] = 1;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].first;
        int d = adj[u][i].second;
        if(vis[v]) continue;
        dist[v] = dist[u] + d;
        dfs(v);
    }
}

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

    for(int i = 0; i < M; i++) {
        int u, v, d; scanf("%d %d %d", &u, &v, &d);
        u--; v--;

        adj[u].push_back(pii(v, d));
        adj[v].push_back(pii(u, -d));
    }

    for(int i = 0; i < N; i++) if(!vis[i]) {
        dist[i] = 0;
        dfs(i);
    }

    for(int u = 0; u < N; u++) {
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            int d = adj[u][i].second;

            if(dist[v] != dist[u] + d) {
                printf("No");
                return 0;
            }
        }
    }
    printf("Yes");
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin>>N;
  string S;
  cin>>S;
  int a=1;
  
  for(int i=0;i<N-1;i++) {
    if(S.at(i)!=S.at(i+1)) {
      a++;
    }
  }
  cout<<a<<endl;
  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>

using namespace std;

int main(){

  int x, y;

  while(1){

    cin >> y >> x;
    if(y == 0 && x == 0) break;

    int data[y][x];

    for(int i = 0; i < y; i++){
      for(int j = 0; j < x; j++){
	cin >> data[i][j];
      }
    }
    int sum[x];
    int sub[x];
    for(int i = 0; i < x; i++) sum[i] = 0;

    for(int i = 0; i < x; i++){
      for(int j = 0; j < y; j++){
	sum[i] += data[j][i];
      }
    }
    for(int i = 0; i < x; i++){
      sub[i] = sum[i];
    }

    sort(sum,sum+x);
    reverse(sum,sum+x);

    for(int i = 0; i < x; i++){
      for(int j = 0; j < x; j++){
	if(sum[i] == sub[j]){
	  sub[j] = -1;
	  cout << j+1;
	  break;
	}
      }
      if(i != x-1) cout << " ";
    }
    cout << endl;

  }
  return 0;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
const ll inf = 8e18;

int n, m;
int a[maxn], b[maxn];

ll dp[1<<12];

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

  cin>>n>>m;
  for (int i=0; i<m; i++) {
    cin>>a[i]; int x; cin>>x;
    int& mask = b[i];
    while (x--) {
      int y; cin>>y; --y;
      mask = mask | (1<<y);
    }
  }

  for (int i=0; i<(1<<12); i++) {
    dp[i] = inf;
  }
  
  dp[0] = 0;

  for (int i=0; i<m; i++) {
    for (int mask=((1<<n)-1); mask>=0; mask--) {
      int _mask = mask | b[i];
      dp[_mask] = min(dp[_mask], dp[mask] + a[i]);
    }
  }

  if (dp[(1<<n)-1] == inf) out(-1);

  cout<<dp[(1<<n)-1]<<endl;

  return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i=0; i<N; i++) {
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  int answer = 0;
  for (int i=0; i<N; i++) {
    if (i < N-1) {
      answer += p.at(i);
    }
    else {
      answer += p.at(i)/2;
    }
  }
  cout << answer << endl;
}

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

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

    int value;
    string mark;

    vector<vector<int>> cards(4, vector<int>(13, 0));

    for (int i = 0; i < n; i++)
    {
        cin >> mark >> value;
        if (mark == "S")
        {
            cards.at(0).at(value - 1) = true;
        }
        else if (mark == "H")
        {
            cards.at(1).at(value - 1) = true;
        }
        else if (mark == "C")
        {
            cards.at(2).at(value - 1) = true;
        }
        else
        {
            cards.at(3).at(value - 1) = true;
        }
    }
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 13; j++)
        {
            if (cards.at(i).at(j) == 0)
            {
                if(i == 0){
                    cout << "S" << " " << j + 1 <<  endl;
                }
                else if(i == 1){
                    cout << "H" << " " << j + 1 << endl;
                }
                else if(i == 2){
                    cout << "C" << " " << j + 1 << endl;
                }
                else {
                    cout << "D" << " " << j + 1 << endl;
                }
            }
        }
    }

    return 0;
}



Measured memory_bytes: 3112
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
	int a, b, k;
	cin >> a >> b >> k;
	for (int i = 0; i < k; ++i)
	{
		if (i%2==0)
		{
			if (a%2==1) a--;
			b += a/2;
			a /= 2;
		}
		else {
			if (b%2==1) b--;
			a += b/2;
			b /= 2;
		}
	}
	cout << a << ' ' << b << endl;
	return 0;
}

Measured memory_bytes: 256