akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr int INF = 2e9;
int main(){ 
  int n, m, x;
  cin >> n >> m >> x;
  int res = INF;

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

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

  for (int bit = 0; bit < (1 << n); bit++) {
    vector<int> tmp(m, 0);
    int sum = 0;

    for (int j = 0; j < n; j++) {
      if (bit & (1 << j)) {
        sum += c[j];
        for (int k = 0; k < m; k++) {
          tmp[k] += a[j][k];
        }
      }
    }

    bool ok = true;

    for (int j = 0; j < m; j++) if (tmp[j] < x) ok = false;

    if (ok) res = min(res, sum);
  }
  cout << (res == INF ? -1 : res) << endl;
  return 0;
} 

Measured memory_bytes: 3636
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

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

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

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

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef tuple<int, int, int> TIII;
typedef vector<int> VI;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

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

int main()
{
    fast_io();
    int X;
    scanf("%d", &X);
    int res = 1, cur = X;
    while (cur % 360)
    {
        res++;
        cur += X;
    }

    printf("%d\n", res);

    return 0;
}

// FOR GNU C++ use the following pattern:
// Uncomment the code below and change your main into main2
// It does not build in MS C++
// But it does increase the stack size from 256 MB on CF and uses GNU C++

//#include <Processthreadsapi.h>
//#include <iostream>
//#include <Synchapi.h>
//#include <windows.h>
//#include <process.h>
//
//DWORD WINAPI MyThreadFunction(LPVOID lpParam) {
//    main2(nullptr);
//    return 0;
//}
//int main() {
//    auto h = CreateThread(nullptr, 1024 << 20, MyThreadFunction, nullptr, STACK_SIZE_PARAM_IS_A_RESERVATION, nullptr);
//    WaitForSingleObject(h, INFINITE);
//}

Measured memory_bytes: 3220
#include <iostream>
using namespace std;
bool is_prime(int n)
{
    if(n<2)
        return false;
    for (int i=2;i*i<=n;i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
int main() {
    int n,N,sw=0;
    cin>>N;
    int array[N];
    for (int i = 0; i <N ; i++) {
        cin>>array[i];
    }
    for (int j = 0; j <N ; j++) {
         n = array[j];
        if (is_prime(n)) {
            sw++;
        }
    }
    cout<<sw<<endl;
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define MAX 100001
int main(){
  vector<bool> b(MAX,true);
  b[0]=b[1]=false;
  for(int i=4;i<MAX;i+=2)  b[i]=false;
  for(int i=3;i<MAX;i+=2){
    if(b[i]){
      for(int j=i*2;j<MAX;j+=i){
        b[j]=false;
      }
    }
  }
  vector<bool> d(MAX);
  for(int i=0;i<MAX;i++){
    if(b[i]&&b[(i+1)/2]) d[i]=true;
    else d[i]=false;
  }
  vector<int> a(MAX);
  int c=0;
  for(int i=0;i<MAX;i++){
    if(d[i]) c++;
    a[i]=c;
  }
  int q,l,r;
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>l>>r;
    cout<<a[r]-a[l-1]<<endl;
  }
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}


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

    int n;
    cin >> n;
    vector<string> v(n);
    
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
        sort(all(v[i]));
    }
    sort(all(v));

    LL c = 1;
    LL res = 0;
    for(int i = 1; i < n; ++i) {
        if(v[i] != v[i - 1]) {
            res += c * (c - 1) / 2;
            c = 1;

        } else {
            c++;

        }
    }
    cout << res + (c * (c - 1) / 2) << endl;

    return 0;
}


Measured memory_bytes: 5760
import math

input_ = input().split()

N = int(input_[0])
D = float(input_[1])

num = 0

for i in range(N):
  x_i,y_i = map(float,input().split())
  
  if(math.sqrt(x_i**2 + y_i**2) <= D):
    num += 1
    
print(num)
  
  


Measured memory_bytes: 9236
#include<bits/stdc++.h>
using namespace std; 
using ll=long long;
#define endl "\n"
#define F(i,n) for(ll i=0;i<n;i++)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repp(i,a,b) for(ll i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define f first
#define s second
#define pll pair<ll,ll>
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()

void solve(){
 
    ll n,flag=0;
    cin>>n;
    
    vll a(n);

    F(i,n)  cin>>a[i];


        F(i,n){
            if(a[i]!=i+1 && flag==0){
                if(a[a[i]-1]!=i+1){
                    cout<<"NO";
                    exit(0);
                }
                else{
                    swap(a[a[i]-1],a[i]);
                    flag=1;
                }
            }
            else if(flag==1 && a[i]!=i+1){
                cout<<"NO";
                exit(0);
            }
        }
        cout<<"YES";

}
signed main(){
    fast;
     
    solve();
 
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define int long long
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18 * 5;

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

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];
    
    int ans = 0;
    for(int i=N-1; i>=0; i--){
        if((A[i]+ans)%B[i]) ans += B[i] - (A[i]+ans)%B[i];
    }
    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>                                                 
int main(void){                                                   
   int H,N,i;                                                     
   scanf("%d %d",&H,&N);                                          
   int A[N];                                                      
   for(i = 0; i < N; i++){                                        
      scanf("%d",&A[i]);                                          
      H -= A[i];                                                  
   }                                                              
   if(H <= 0){                                                    
      printf("Yes");                                              
   }else{                                                         
      printf("No");                                               
   }                                                              
   return 0;                                                      
}

Measured memory_bytes: 2068
#include<stdio.h>
#include<string.h>
int main(void){
	int k,i, n = 0, f;
	char s[12];
	char c[100];
	scanf("%s", s);
for(k=0;k<12;k++){
if('a'<=s[k]&&s[k]<='z'){s[k]=s[k]-'a'+'A';}
}
	while (1){
		scanf("%s", c);
f = strcmp(c, "END_OF_TEXT");
		if (f == 0){ break; }
for(k=0;k<100;k++){
if('a'<=c[k]&&c[k]<='z'){c[k]=c[k]-'a'+'A';}else if(c[k]=='\0'){break;}
}
		i = strcmp(c, s);
		
		if (i ==0){ n += 1; i = '\0'; }
	}
	printf("%d\n", n);
	return 0;
}

Measured memory_bytes: 548
def examA():
    N = I()
    ans = (10000 - N)%1000
    print(ans)
    return

def examB():
    T = ["AC","WA","TLE","RE"]
    N = I()
    S = [SI()for _ in range(N)]

    ans = [0]*4
    for s in S:
        for i in range(4):
            if s==T[i]:
                ans[i] += 1
                break
    for i in range(4):
        print(T[i]+" x "+str(ans[i]))
    return

def examC():
    H, W, K = LI()
    C = [[""]*W for _ in range(H)]
    for h in range(H):
        S = SI()
        for w in range(W):
            C[h][w] = S[w]
    ans = 0
    #print(C)
    for hi in range(1<<H):
        nowC = deepcopy(C)
        for h in range(H):
            if hi&(1<<h):
                for i in range(W):
                    nowC[h][i] = "R"
        for wi in range(1 << W):
            nowCC = deepcopy(nowC)
            for w in range(W):
                if wi & (1 << w):
                    for i in range(H):
                        nowCC[i][w] = "R"
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if nowCC[h][w] == "#":
                        cnt += 1
            if cnt == K:
                #print(hi, wi, nowCC)
                ans += 1
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 80760
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    mp = [S() for _ in range(h)]

    def search(ss):
        d = collections.defaultdict(lambda: inf)
        q = []
        for s in ss:
            d[s] = 0
            heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for di,dj in dd:
                ni = u[0] + di
                nj = u[1] + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w or mp[ni][nj] == '#':
                    continue
                uv = (ni, nj)
                if v[uv]:
                    continue
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    ss = []
    ps = None
    es = None
    for i in range(h):
        for j in range(w):
            if mp[i][j] == '$':
                ss.append((i,j))
            elif mp[i][j] == '@':
                ps = (i,j)
            elif mp[i][j] == '%':
                es = (i,j)
    pd = search(ss)
    d = search([ps])
    if d[es] < pd[es]:
        return 'Yes'

    return 'No'


print(main())




Measured memory_bytes: 18360
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
typedef long long LL;

int main(int argc, char* argv[]) {
	LL n, ans = 0;
	cin >> n;
	vector<LL> p;
	for (LL x = 2; x <= 1000000; ++x) {
		int c = 0, d = 1;
		while ((n % x) == 0) {
			n /= x;
			if (++c == d) {
				++ans;
				c = 0;
				++d;
			}
		}
	}
	if (n > 1) {
		++ans;
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, o = 0;
  string s;
  cin >> n >> s;
  for(int i = 0; i < 10; i++) {
    auto a = find(s.begin(), s.end(), '0' + i);
    if(a != s.end() - 2) {
      for(int j = 0; j < 10; j++) {
        auto b = find(a + 1, s.end(), '0' + j);
        if(b != s.end() - 1) {
          for(int k = 0; k < 10; k++) {
            auto c = find(b + 1, s.end(), '0' + k);
            if(c != s.end()) o++;
          }
        }
      }
    }
  }
  cout << o << '\n';
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1LL<<60;

template<typename Abel>
struct WeightedUnionFind{
    int num;
    vector<int> par,rank;
    vector<Abel> diff_weight;
    WeightedUnionFind(int n,Abel id=0):
        num(n),par(n),rank(n,1),diff_weight(n,Abel(0)){
        iota(par.begin(),par.end(),0);
    }
    int root(int x){
        if (x==par[x]) return x;
        int t=root(par[x]);
        diff_weight[x]+=diff_weight[par[x]];
        return par[x]=t;
    }
    bool merge(int x,int y,Abel w){
        w+=weight(x),w-=weight(y);
        x=root(x),y=root(y);
        if (x==y) return false;
        if (rank[x]<rank[y]) swap(x,y),w=-w;
        par[y]=x;
        rank[x]+=rank[y];
        diff_weight[y]=w;
        --num;
        return true;
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    Abel weight(int x){
        root(x);
        return diff_weight[x];
    }
    Abel diff(int x,int y){
        return weight(y)-weight(x);
    }
    int size(int x){
        return rank[root(x)];
    }
    int count(){
        return num;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int R,C,N; cin >> R >> C >> N;
    vector<vector<pair<int,ll>>> col(R),row(C);
    for (int i=0;i<N;++i){
        int r,c; ll a; cin >> r >> c >> a; --r,--c;
        col[r].emplace_back(c,a);
        row[c].emplace_back(r,a);
    }
    WeightedUnionFind<ll> ufc(C),ufr(R);
    for (int i=0;i<R;++i){
        for (int j=0;j+1<col[i].size();++j){
            ll d=col[i][j+1].second-col[i][j].second;
            int l=col[i][j].first,r=col[i][j+1].first;
            if (!ufc.same(l,r)) ufc.merge(l,r,d);
            else if (ufc.diff(l,r)!=d){
                cout << "No" << '\n';
                return 0;
            }
        }
    }
    for (int i=0;i<C;++i){
        for (int j=0;j+1<row[i].size();++j){
            ll d=row[i][j+1].second-row[i][j].second;
            int l=row[i][j].first,r=row[i][j+1].first;
            if (!ufr.same(l,r)) ufr.merge(l,r,d);
            else if (ufr.diff(l,r)!=d){
                cout << "No" << '\n';
                return 0;
            }
        }
    }
    vector<ll> Minc(C,INF),Minr(R,INF);
    for (int i=0;i<R;++i){
        for (int j=0;j<col[i].size();++j){
            int id=col[i][j].first,p=ufc.root(id);
            Minc[p]=min(Minc[p],ufc.diff(p,id));
        }
    }
    for (int i=0;i<R;++i){
        for (int j=0;j<col[i].size();++j){
            int id=col[i][j].first,p=ufc.root(id);
            if (col[i][j].second+ufc.diff(id,p)+Minc[p]<0){
                cout << "No" << '\n'; return 0;
            }
        }
    }
    for (int i=0;i<C;++i){
        for (int j=0;j<row[i].size();++j){
            int id=row[i][j].first,p=ufr.root(id);
            Minr[p]=min(Minr[p],ufr.diff(p,id));
        }
    }
    for (int i=0;i<C;++i){
        for (int j=0;j<row[i].size();++j){
            int id=row[i][j].first,p=ufr.root(id);
            if (row[i][j].second+ufr.diff(id,p)+Minr[p]<0){
                cout << "No" << '\n'; return 0;
            }
        }
    }
    cout << "Yes" << '\n';
}

Measured memory_bytes: 15872
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000010

int m;
vector<int> A;

void update(int a,int b){
  A[m+a]=b;
  int j=(m+a)/2;
  while(j>=1){
    A[j]=min(A[2*j],A[2*j+1]);
    j/=2;
  }  
}

int find(int a,int b,int k,int l,int r){
  if(b<=l || r<=a) return INF;
  else if(a<=l && b>=r) return A[k];
  else{
    int c1=find(a,b,2*k,l,(l+r)/2);
    int c2=find(a,b,2*k+1,(l+r)/2,r);
    return min(c1,c2);
  }
}         

int main(){
  int n,l;
  cin>>n>>l;
  
  m=1;
  while(m<n){
    m*=2;
  }
  
  A=vector<int>(2*m,INF);
  
  int x;
  rep(i,n){
    cin>>x;
    update(i,x);
  }
  
  for(int i=1;i<=n-l+1;i++){
    if(i!=1) cout<<" ";
    cout<<find(i,i+l,1,1,m+1);
  }
  cout<<endl;
  
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      if (i * j == n) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3608
#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(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    int ans = 0;
    while(n > 0){
        n /= k;
        ans++;
    }
    PRINT(ans);
}

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

#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define let const auto
#define USE_T template <typename T>
#define USE_Ti template <typename T = int>
#define USE_TU template <typename T, typename U>

USE_Ti using duo = std::pair<T, T>;
USE_Ti using vec = std::vector<T>;
using ll = long long;
// clang-format off
USE_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE_Ti inline T in(){T x;std::cin>>x;return x;}
USE_Ti inline vec<T> in(int n){vec<T> v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE_T inline void in(T*x,int n){rep(i,n)x[i]=in<T>();}
struct IoSetup {
  IoSetup(){
    using namespace std;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<setprecision(10);
    cerr<<setprecision(10);
  }
} iosetup;
// clang-format on
// }}}
using namespace std;
const int inf = 1001001001;
const ll infll = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  int N = in(), M = in();
  auto D = in(N);
  auto C = in(M);
  vec<vec<int>> dp(M + 1, vec<int>(N + 1, inf));
  dp[0][0] = 0;
  REP(d, M) {
    REP(t, N) {
      chmin(dp[d + 1][t], dp[d][t]);
      chmin(dp[d + 1][t + 1], dp[d][t] + D[t] * C[d]);
    }
    chmin(dp[d + 1][N], dp[d][N]);
  }
  cout << dp[M][N] << endl;

  return 0;
}

Measured memory_bytes: 5764
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template < typename T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    int len = comma - names;
    for (int i = 0; i < len; ++i) {
        cout << names[i];
    }
    cout <<  " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;

#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) (sort(x.begin(), x.end()), x.resize(distance(x.begin(), unique(x.begin(), x.end()))))
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const ll LINF = LLONG_MAX, base = 1e9, MOD = 1e9 + 7, N = 1e5 + 10, M = 1e3 + 10;
const int INF = INT_MAX;
const db PI = acos(-1);

void test();

int main() {
    fast_io();
    test();
    return 0;
}

void test() {
    int a, p;
    cin >> a >> p;
    cout << (a * 3 + p) / 2 << "\n";
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int r, c;
  scanf("%d %d", &r, &c);

  int arr[r+1][c+1], i, j;
  for (i=0; i<c+1; i++) {
    arr[r][i]=0;
  }

  for (i=0; i<r; i++) {
    int sum=0;
    for (j=0; j<c; j++) {
      scanf("%d", &arr[i][j]);
      sum+=arr[i][j];
      arr[r][j]+=arr[i][j];
    }
    arr[i][j]=sum;
    arr[r][c]+=sum;
  }

  for (i=0; i<r+1; i++) {
    for (j=0; j<c+1; j++) {
      if (j<c) {
        printf("%d ", arr[i][j]);
      } else {
        printf("%d\n", arr[i][j]);
      }
    }
  }
  return 0;
}


Measured memory_bytes: 2048
//https://atcoder.jp/contests/abc155/tasks/abc155_a

#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <algorithm>

using namespace std;

int main ()
{

    int N, ans;

    cin >> N;

    ans = N / 2;
    ans += N % 2;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
  long long int n,c;
  cin>>n;
  if(n%2==0)
  {
      c=n;
  }
  else
  {
      c=n*2;
  }
  cout<<c<<endl;
    return 0;

}







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


using namespace std;


int main() {

    int n, a[100+5], i, cost1, cost2;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    cost1 = cost2 = 0;

    for (i = 1; i < n; ++i) {
        if (a[i] == a[i-1]) {
            ++cost1;
            ++i;
        }
    }
    for (i = n-1; i >= 0; --i) {
        if (a[i] == a[i-1]) {
            ++cost2;
            --i;
        }
    }
    cout << min(cost1, cost2) << endl;

    return (0);
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

#define pll pair<ll,ll>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define rep(i,n) for (int i = 0; i < n; ++i) 
#define REP(i,k,n) for (int i = k; i <= n; ++i) 
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
#define sz(a) int((a).size())
#define endl '\n' // remove for interactive

const int INF = 1e9;
const ll mod = 1e9 + 7;
ll powmod(ll a,ll b) {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;}



void solve()
{
    int x; cin>>x;
    cout<<!x;
}

int main()
{
    // clock_t start, end;
    // start = clock();
    ios_base::sync_with_stdio(0); //cant use scanf, printf
    cin.tie(0);cout.tie(0); // no longer auto flush cout before each cin, remove for interactive
    int t = 1;
    // cin>>t;
    REP(i, 1, t)
    {
        solve();
        
    }
    // end = clock();
    // double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    // watch(time_taken);
    ll x = INF; x++;
    return 0;
    
}



/*before sub
TEST: 0(1 by 1 too), 1, equal, -ve, bounds(random and ez)
ERR/WA: loop vars, out of bounds, endl, finish taking inputs, large doubles, larger INF, corr mod, t, early/late mod
RE: double dec, integer overflow(ll or 1LL mult)
*/





Measured memory_bytes: 3648
from collections import defaultdict

def main():
    N = int(input())
    d = defaultdict(lambda: 0)
    for _ in range(N):
        d["".join(sorted(list(input())))]+=1

    ans = 0

    for v in d.values():
        ans += v*(v-1)//2

    print(ans)







if __name__ == '__main__':
    main()

Measured memory_bytes: 22500
#include <bits/stdc++.h>
#define ll long long

#define INF 999999999

using namespace std;

// input
string s;

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

    cin >> s;

    string ans = (s[0] == s[2])?"Yes":"No";
    cout << ans << "\n";
    
}

Measured memory_bytes: 256
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdio.h>


using namespace std;

int main(void) {
    int K,A,B;
    cin>>K>>A>>B;
    int ans=0;

    for(int i=A;i<=B;i++){
        if(i%K==0){
            ans++;
        }
    }

    if(ans==0){
        cout<<"NG"<<endl;
    }else{
        cout<<"OK"<<endl;
    }

}


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

int main() {
int64_t x,k,d,a;
  cin>>x>>k>>d;
  if((x+d*k>0&&x-d*k<0)||(x+d*k<0&&x-d*k>0)){if(((abs(x)/d)-k)%2==0){cout<<abs(x)%d<<endl;}
  else{cout<<d-(abs(x)%d)<<endl;}}
  else{cout<<min(abs(x+d*k),abs(x-d*k))<<endl;}  
}

Measured memory_bytes: 3560
S = input()

if S == "SUN":
    print('7')

if S == "MON":
    print('6')
    
if S == "TUE":
    print('5')
    
if S == "WED":
    print('4')
    
if S == "THU":
    print('3')
    
if S == "FRI":
    print('2')
    
if S == "SAT":
    print('1')


Measured memory_bytes: 2940
#include<iostream>
#include<queue>
#define mp(a,b) make_pair(a,b)
using namespace std;
struct xy{
  int x,y,f;
  bool operator<(const xy& a)const{
    return true;
  }
};
typedef pair<int, xy > P;

int w,h;
bool in(xy a){
  if(a.x<0||a.x>=w||a.y<0||a.y>=h) return false;
  return true;
}

int main(){
  int inf = 1<<20;
  cin >> w >> h;
  while(w!=0){
    char st[30][60];
    char c;
    int i,j,k;
    int d[31][61][2];
    fill(d[0][0],d[30][60],inf);
    priority_queue<P,vector<P>,greater<P> > q;

    xy v,b;

    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	cin >> st[j][i];
	if(st[j][i]=='S'){
	  v.x=j;v.y=i;v.f=0;
	  q.push(mp(0,v));
	  v.f=1;
	  q.push(mp(0,v));
	  d[j][i][0]=0;
	  d[j][i][1]=0;
	}
      }
    }
    int o=inf;
    while(!q.empty()){
      P p=q.top();q.pop();
      v = p.second;
      if(d[v.x][v.y][v.f] < p.first) continue;
      d[v.x][v.y][v.f]=p.first;
      if(v.f==0){
	for(i=1;i<=3;i++){
	  for(j=-3+i;j<=3-i;j++){
	    b.x=v.x+i;b.y=v.y+j;b.f=1;
	    if(in(b)){
	      if(st[b.x][b.y]=='T'){
		o=min(o,p.first);
	      }else{
		int g;
		if(st[b.x][b.y]=='S') g=0;
		else if(st[b.x][b.y]=='X') g=inf;
		else g=st[b.x][b.y]-'0';
		if(d[b.x][b.y][b.f] > d[v.x][v.y][v.f]+g){
		  d[b.x][b.y][b.f] = d[v.x][v.y][v.f]+g;
		  q.push(mp(d[b.x][b.y][b.f],b));
		}
	      }
	    }
	  }
	}
      }else{
	for(i=1;i<=3;i++){
	  for(j=-3+i;j<=3-i;j++){
	    b.x=v.x-i;b.y=v.y+j;b.f=0;
	    if(in(b)){
	      if(st[b.x][b.y]=='T'){
		o=min(o,p.first);
	      }else{
		int g;
		if(st[b.x][b.y]=='S') g=0;
		else if(st[b.x][b.y]=='X') g=inf;
		else g=st[b.x][b.y]-'0';
		if(d[b.x][b.y][b.f] > d[v.x][v.y][v.f]+g){
		  d[b.x][b.y][b.f] = d[v.x][v.y][v.f]+g;
		  q.push(mp(d[b.x][b.y][b.f],b));
		}
	      }
	    }
	  }
	}
      }
    }
    if(o==inf) cout << -1 << endl;
    else cout << o << endl;
    cin >> w >> h;
  }

}

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

int main() {
  int N = 0,count = 1;
  cin >> N;
  vector<int>A(N);
  rep(i,N){
    cin >> A[i];
    if(A[i] % 2 == 0){
      count *= 2;
    }
  }
  cout << pow(3,N) - count;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rgi register int
#define ll long long
#define il inline

using namespace std;

int n, len, ans;
string str;

il int read() {
	rgi x = 0, f = 0, ch;
	while(!isdigit(ch = getchar()))	f |= ch == '-';
	while(isdigit(ch))	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int main() {
	n = read();
	cin >> str; len = str.length(); ans = len;
	for(rgi i = 0; i < len - 1; ++i) {
		if(str[i + 1] == str[i])
			ans--;
	}
	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    string S;
    cin >> S;
    if(S == "SUN")
    {
        cout << 7 << endl;
    }
    else if(S == "SAT")
    {
        cout << 1 << endl;
    }
    else if(S == "FRI")
    {
        cout << 2 << endl;
    }
    else if(S == "THU")
    {
        cout << 3 << endl;
    }
    else if(S == "WED")
    {
        cout << 4 << endl;
    }
    else if(S == "TUE")
    {
        cout << 5 << endl;
    }
    else if(S == "MON")
    {
        cout << 6 << endl;
    }
#ifdef TEST

switch    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

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

int main() {
  int N ,A;
  cin >>N>>A;
  if (N % 500==0)
    cout<<"Yes"<<endl;
  else if (N % 500<=A)
    cout<<"Yes"<<endl;
  else if (N % 500>A)
    cout<<"No"<<endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


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

  int n,m,r;
  cin>>n>>m>>r;

  vector<int> p(r);
  rep(i,r){
    cin>>p[i];
    p[i]--;
  }

//———————ワーシャルフロイド法　O(N^3)—————————————————

  vector<vector<ll>> dist(n,vector<ll>(n,INF));
  rep(i,n){
    dist[i][i]=0;
  }

  rep(i,m){
    ll a,b,c;
    cin>>a>>b>>c;
    dist[a-1][b-1]=c;
    dist[b-1][a-1]=c;
  }

  rep(i,n){
    rep(j,n){
      rep(k,n){
        dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
        dist[k][j]=dist[j][k];
      }
    }
  }


  ll ans=INF;

//——————————————next_permutaion(np)——————————————
  sort(all(p));
  
  do{
  ll sum=0;
  rep(i,r-1){
    sum+=dist[p[i]][p[i+1]];
  }
  chmin(ans,sum);
  }while(np(all(p)));

//——————————————————————————————————————————

  cout << ans << endl;
}

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

using namespace std;

int main()
{
   int a, b;
   char c;
   scanf("%d %c %d",&a,&c,&b);
   if(c=='+')
   {
      cout<<a+b;
   }
   else if(c=='-')
   {
       cout<<a-b;
   }

   return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=1;i<=n;i++)
using namespace std;

int main(){
    int a,b; cin >> a >> b;
    if(a>9 || b>9) cout << -1 << endl;
    else cout << a*b << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[m];
		int[] b = new int[m];
		int[] count = new int[n + 1];
		for (int i = 0; i < m; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			count[a[i]]++;
			count[b[i]]++;
		}
		int ans = 0;
		boolean bre = true;
		while (bre) {
			bre = false;
			out: for (int i = 0; i <= n; i++) {
				if (count[i] == 1) {
					count[i]--;
					ans++;
					for (int j = 0; j < m; j++) {
						if (a[j] == i) {
							count[b[j]]--;
							a[j] = 0;
							b[j] = 0;
							bre = true;
							break out;
						} else if (b[j] == i) {
							count[a[j]]--;
							a[j] = 0;
							b[j] = 0;
							bre = true;
							break out;
						}
					}
				}
			}
		}
		System.out.println(ans);

	}
}

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

map<long long, int> mmp;

int main(void) {
	int n; cin >> n;
	mmp[0]++; 
	long long s = 0, ans = 0;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x; s += x;
		ans += mmp[s]; ++mmp[s]; }
	cout << ans;
	return 0; }
		


Measured memory_bytes: 12800
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs

const int MAXN = 105;

int n;
int a[MAXN];
int ans;

void calc(int l, int r) {
  if (l > r) {
    return;
  }
  int mn = a[l];
  for (int i = l; i <= r; i++) {
    mn = min(mn, a[i]);
  }
  ans += mn;
  for (int i = l; i <= r; i++) {
    a[i] -= mn;
  }
  for (int i = l; i <= r; i++) {
    if (a[i] == 0) {
      calc(l, i - 1);
      calc(i + 1, r);
      return;
    }
  }
}

int main() { 

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

  calc(0, n - 1);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
n, w = map(int, input().split())

weight_value = [0] * n
for i in range(n):
  weight_value[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
  for w_upper in range(w+1):
    if w_upper - weight_value[i][0] >= 0:
      dp[i+1][w_upper] = max(dp[i][w_upper - weight_value[i][0]] + weight_value[i][1], dp[i][w_upper])
    else:
      dp[i+1][w_upper] = dp[i][w_upper]
print(dp[n][w])
      

Measured memory_bytes: 120044
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
 
ll MOD = 1000000007;
ll INF =1<<29;

int main() {
     int n;
     cin >> n;
     vector<int> b(n-1);
     rep(i,n-1) cin >> b[i];

     int ans = b[0];
     rep(i,n-2){
         ans += min (b[i],b[i+1]);
     }
     cout << ans + b[n-2] <<endl;
}

Measured memory_bytes: 256
#coding:utf-8
import math
import string
import time
import fractions

n, x = map(int,raw_input().split())
a = map(int,raw_input().split())


ans = 0
for i in range(len(a) - 1):
	if a[i] + a[i + 1] > x:
		kosuu = (a[i] + a[i + 1]) - x
		if a[i+1] >= kosuu:
			a[i+1] -= kosuu
		else:
			a[i] = a[i] - (kosuu-a[i+1])
			a[i+1] = 0
		ans += kosuu
print ans

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

const int MAXN = 300010;
const int mod = 1000000007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int pow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
int remod(LL x) { x %= mod; return x + (x >> 63 & mod); }
const int MAXS = 1000010;
int fac[MAXS], inv[MAXS];
int n, m, K;
int C(int a, int b) { return a < b ? 0 :(LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXS; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXS; ++i) inv[i] = mul(inv[i - 1], inv[i]);
	std::cin >> n >> m >> K;
	int ans = 0, now = 0;
	for (int i = 0; i <= m + K; ++i) {
		reduce(now += now - mod);
		if (i) reduce(now -= C(i - 1, std::min(i - 1, m)));
		if (i > K) reduce(now -= C(i - 1, i - K - 1));
		if (i <= m) reduce(now += 1 - mod);
		reduce(ans += pow(3, m + K - i, mul(C(i + n - 1, n - 1), now)) - mod);
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;
  if (e-a<=k){
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MODNum 1000000007
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    ll N, ans;
    cin >> N;
    vector<int> dp(N+1,INT_MAX);
    dp.at(0) = 0;
    REP(int,i,1,N+1){
        for ( int pow6 = 1; pow6 <= N; pow6 *= 6 ){
            if ( i - pow6 < 0 ) break;
            dp.at(i) = min(dp.at(i), dp.at(i-pow6)+1);
        }
        for ( int pow9 = 1; pow9 <= N; pow9 *= 9 ){
            if ( i - pow9 < 0 ) break;
            dp.at(i) = min(dp.at(i), dp.at(i-pow9)+1);
        }
    }
    cout << dp.at(N) << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int mod = 1e9+7;
vector<int> edge[maxn];
int n,k;
long long result;

void dfs(int curr,int pst,int ct){
  for(auto i:edge[curr]){
      if(i!=pst){
        
        if(ct == 0){
          result = 0;
          return ;
        }

        result = (1LL * result * ct) % mod;
        dfs(i,curr,k-2);
        ct--;
      }
  }
  
}


int main(){
  cin>>n>>k;
  for(int i=0;i<n-1;++i){
    int f,t;
    cin>>f>>t;
    edge[f].push_back(t);
    edge[t].push_back(f);
  }
  result = k;
  dfs(1,0,k-1);
  cout<<result<<endl;
  
  return 0; 
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

int n;
const int mod = 1e9 + 7;

signed main(){
    cin >> n;
    vector<int> t(n), a(n), d(n, 0);
    vector<bool> f(n, false);
    bool g = true;
    int ans = 1;
    rep(i, 0, n){
        cin >> t[i];
    }
    rep(i, 0, n){
        cin >> a[i];
    }
    d[0] = t[0];
    rep(i, 1, n){
        if(t[i] != t[i - 1]){
            d[i] = t[i];
        }
    }
    if(d[n - 1] != 0 && d[n - 1] != a[n - 1]) g = false;
    else d[n - 1] = a[n - 1];
    repb(i, n - 2, 0){
        if(d[i] != 0 && d[i] > a[i]) g = false;
        if(a[i] != a[i + 1]){
            if(d[i] != 0 && d[i] != a[i]) g = false;
            d[i] = a[i];
        }
    }
    
    // rep(i, 0, n){
    //     cout << i << d[i] << endl;
    // }
    rep(i, 0, n){
        if(d[i] == 0){
            ans = (ans * min(a[i], t[i])) % mod;
        }
    }
    if(g == false) o(0);
    else o(ans);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int A,B;

int C;

int main(){
  cin >> A >> B >> C;

  rep(i,0,B){
    if((A * i) % B == C){
      cout << "YES" << endl;
      return 0;
    }
  }

  cout << "NO" << endl;


}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int ans;
int a[5][5];


int main(void) {
	int N;
	rep(i, 0, 3) rep(j, 0, 3) {
		cin >> a[i][j];
	}
	cin >> N;
	rep(i, 0, N) {
		int b;
		cin >> b;
		rep(i, 0, 3) rep(j, 0, 3) {
			if (a[i][j] == b) a[i][j] = -1;
		}
	}
	bool ok = false;
	rep(i, 0, 3) {
			if (a[i][0] == a[i][1] && a[i][0] == a[i][2]) ok = true;
			if (a[0][i] == a[1][i] && a[0][i] == a[2][i]) ok = true;
	}
	if (a[0][0] == a[1][1] && a[0][0] == a[2][2]) ok = true;
	if (a[0][2] == a[1][1] && a[0][2] == a[2][0]) ok = true;
  
    if (ok) puts("Yes");
    else puts("No");

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
ll factorial(int i) {       //階乗
    if (i == 0) return 1;
    return (factorial(i - 1)) * i;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n); 
    int a[110000];
    ll ans = 0;
    rep(i, n) {
        cin >> A[i];
        a[A[i]]++;
        ans += A[i];
    }
    int q;
    cin >> q;
    vector<vector<int>> d(q, vector<int> (2));
    rep(i, q) cin >> d[i][0] >> d[i][1];
    rep(i, q) {
        ans += (d[i][1] - d[i][0]) * a[d[i][0]];
        a[d[i][1]] += a[d[i][0]];
        a[d[i][0]] = 0;
        cout << ans << endl;
    }  
}

Measured memory_bytes: 9548
import java.util.*;
import java.io.*;
public class Main{
    static class Event implements Comparable<Event>{
        long x;
        int i;
        public Event(long _x, int _i){
            x = _x;
            i = _i;
        }
        public int compareTo(Event other){
            return x-other.x>0?1:x-other.x<0?-1:0;
        }
        
    }

    public static void main(String[] args) {
        FastReader in = new FastReader(System.in);
        int a = in.nextInt(), b = in.nextInt(), q = in.nextInt();
        long[] s = new long[100005], t = new long[100005];
        Event[] x = new Event[100005];
        s[0] = -(long)(1e11);
        s[a+1] = (long)(1e11);
        for (int l = 1; l <= a; ++l){
            s[l] = in.nextLong();
        }
        t[0] = -(long)(1e11);
        t[b+1] = (long)(1e11);
        for (int l = 1; l <= b; ++l){
            t[l] = in.nextLong();
        }
        for (int l = 0; l < q; ++l){
            x[l] = new Event(in.nextLong(), l);
        }
        Arrays.sort(x, 0, q);


        int posS = 1, posT = 1;
        long[] answer = new long[100005];
        for (int l = 0; l < q; ++l){
            while(s[posS] < x[l].x) posS++;
            while(t[posT] < x[l].x) posT++;
            answer[x[l].i] = Math.min(
               Math.min(
                   Math.max(s[posS], t[posT]) - x[l].x,
                   x[l].x - Math.min(s[posS-1], t[posT-1])
               ),
               Math.min(
                   Math.min(
                       s[posS] - x[l].x + s[posS] - t[posT-1],
                       t[posT] - x[l].x + t[posT] - s[posS-1]
                   ),
                   Math.min(
                       x[l].x - s[posS-1] + t[posT] - s[posS-1],
                       x[l].x - t[posT-1] + s[posS] - t[posT-1]
                   )
               )
            );
        }
        for (int l = 0; l < q; ++l){
            System.out.println(answer[l]);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(InputStream I) {
            br = new BufferedReader(new InputStreamReader(I));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

Measured memory_bytes: 54932