akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
using Weight=int;
struct Edge {
    int src,dest; Weight weight;
    bool operator<(const Edge &rhs)const{
        return weight<rhs.weight;
    }
};
using Edges=vector<Edge>;
using Graph=vector<Edges>;
 
const Weight INF=1e9;
 
void Dijkstra(const Graph &g,int s,vector<Weight> &d){
    assert(0<=s && s<g.size());
    d.assign(g.size(),INF); d[s]=0;
    vector<int> used(g.size(),0);
    using P=pair<Weight,int>;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty()){  
        auto val=que.top(); que.pop();
        Weight dist=val.first;
        int v=val.second;
        if(used[v]) continue;
        used[v]=true;
        for(auto e:g[v]){
            int to=e.dest;
            Weight w=e.weight;
            if(dist+w<d[to]){
                d[to]=dist+w;
                que.push({d[to],to});
            }
        }
    }
}

vector<Weight> Dijkstra(const Graph& g,int s){
    vector<Weight> res;
    Dijkstra(g,s,res);
    return res;
}

vector<Weight> DijkstraPath(const Graph &g,int s,vector<int> &prev){
    prev.assign(g.size(),-1);
    prev[s]=s;
    vector<Weight> d(g.size(),INF);
    assert(0<=s && s<g.size());
    d[s]=0;
    vector<int> used(g.size(),0);
    using P=pair<Weight,int>;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty()){  
        auto val=que.top(); que.pop();
        Weight dist=val.first;
        int v=val.second;
        if(used[v]) continue;
        used[v]=true;
        for(auto e:g[v]){
            int to=e.dest;
            Weight w=e.weight;
            if(dist+w<d[to]){
                prev[to]=v;
                d[to]=dist+w;
                que.push({d[to],to});
            }
        }
    }
    return d;
}

vector<int> BuildPath(int s,int t,vector<int> &prev){
    vector<int> res;
    if(prev[s]==-1) return res;
    int v=t;
    while(v!=s){
        res.push_back(v);
        v=prev[v];
    }
    res.push_back(s);
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    int n;
    cin>>n;
    Graph g(n);
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k>>k;
        for(int j=0;j<k;j++)
        {
            int v;
            cin>>v;  
            Weight c;
            cin>>c;          
            g[i].push_back((Edge){i,v,c});
        }
    }
    vector<Weight> d;
    vector<int> prev;
    d=DijkstraPath(g,0,prev);
    for(int i=0;i<n;i++)
    {
        cout<<i<<" "<<d[i]<<endl;
        /*
        vector<int> path=BuildPath(0,i,prev);
        for(int i=0;i<path.size();i++) cout<<path[i]<<" ";
        cout<<endl;
        */
    }
    return 0;
}

Measured memory_bytes: 9892
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define vec vector 


void solve(){
    int n, m;
    cin >>n >> m;
    int a[n];
    int total_votes = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        total_votes += a[i];
    }
    double min_votes = 1.0/(4 * m) * total_votes;
    sort(a, a + n, greater<int>());
    for(int i = 0; i < m; ++i){
        if(a[i] < min_votes){
            //cout << a[i] << ' ' << min_votes << endl;
            cout << "No" << endl;
            return ;
        }
    }
    cout << "Yes" << endl;
}

int main(){
    clock_t startTime = clock();
    solve();
    //cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
// headers {{{
using namespace std;
// using namespace rel_ops;
 
typedef long long int64;
typedef unsigned long long uint64;
const double pi=acos(-1.0);
const double eps=1e-11;
const int INF=0x7FFFFFFF;
template<class T> inline bool checkmin(T &a,T b){return b<a?a=b,1:0;}
template<class T> inline bool checkmax(T &a,T b){return b>a?a=b,1:0;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define mem(a,b) memset(a, b, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define repit(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define iter(v) typeof(v.begin())
#define ff first
#define ss second
#ifdef LOCAL
#define dbg(args...) printf(args); //##__VA_ARGS__
#define dout cout
#define out(x) (cout<<#x<<": "<<x<<endl)
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
#else
#define dbg(...)
#define dout if(true);else cout
#define out(...)
#define show(...)
#endif
// }}}

struct B {
    B* p[3] = {};
    int idx;
    bool rev = false;
    void push() {
        if (rev) {
            swap(p[1], p[2]);
            for (auto c : p) if (rev && c) c->reverse();
            rev = 0;
        }
    }
    void reverse() {
        rev ^= 1;
    }
};

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL); 
    int N;
    while (cin >> N) {
		int tot = 1;
        rep(i, N) tot *= 3;
        B root;
        rep(i, tot) {
            B* s = &root;
            int c = i;
            rep(j, N) {
                int k = c % 3; c /= 3;
                if (!s->p[k]) s->p[k] = new B();
                s = s->p[k];
            }
            s->idx = i;
        }
        string t; cin >> t;
        rep(i, t.length()) {
            if (t[i] == 'S') root.reverse();
            else {
                B* c = &root;
                rep(i, N) {
                    c->push();
                    B* tmp = c->p[2];
                    c->p[2] = c->p[1];
                    c->p[1] = c->p[0];
                    c->p[0] = tmp;
                    c = c->p[0];
                }
            }
        }
        VI pos(tot);
        rep(i, tot) {
            B* s = &root;
            int c = i;
            rep(j, N) {
                s->push();
                int k = c % 3; c /= 3;
                s = s->p[k];
            }
            pos[s->idx] = i;
        }
        rep(i, tot) cout << pos[i] << ' ';
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 43808
#include<stdio.h>

int main(){
  while(1){
    int n;
    scanf("%d", &n);
    if(n!=0){
      int i,k;
      int a, b, c;
      int j=0;
      int d[4001]={};
      double e[4001] ={};
      int flag = 0;
      for(i=0;i<n;i++){
	scanf("%d %d %d", &a, &b, &c);
	int flag1=0;
	for(k=0;k<j;k++){
	  if(d[k]==a)
	    flag1=1;
	}
	if(flag1==0)
	  {d[j]=a;j++;}

	//if(e[a]+b*c<=2147483647)
	e[a]=e[a]+(double)b*(double)c;
	//else
	  //e[a]=(double)2147483647;//printf("aa\n");
	
      }


      for(i=0;i<4001;i++){
	if(e[d[i]]>=1000000.){
	  printf("%d\n", d[i]);
	  flag++;
	}
      }
      if(flag==0)
	printf("NA\n");
      
    }
    else{
      break;
    }
  }
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main(){
    string s;
    cin >> s;
    for (int i = 0; i < 3; ++i) {
        if (s[i] == s[i+1]) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
}

Measured memory_bytes: 3468
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node{
    int key;
    Node *p,*l,*r;
};
Node *root,*NIL;
void insert(int key){
    Node *y = NIL;//根节点的父节点
    Node *x = root;//根节点
    Node *z = (Node *)malloc(sizeof(Node));
    z->key = key;
    z->l = NIL;
    z->r = NIL;
    while(x!=NIL){
        y = x;//记录key的父节点
        if(z->key<x->key){
            x = x->l;//寻找key的父节点
        }else{
            x = x->r;
        }
    }
    z->p = y;
    if(y == NIL){
        root = z;
    }else if(y->key<z->key){//决定是左儿子还是右二子
        y->r = z;
    }else{
        y->l = z;
    }
}
void preTW(Node *u){
    if(u!=NIL){
        cout<<" "<<u->key;
        preTW(u->l);
        preTW(u->r);
    }
}
void inTW(Node *u){
    if(u!=NIL){
        inTW(u->l);
        cout<<" "<<u->key;
        inTW(u->r);
    }
}
Node* findx(Node *x,int key){
    while(x!=NIL&&x->key!=key){
        if(key<x->key){
            x = x->l;
        }else{
            x = x->r;
        }
    }
    return x;
}
Node * getMin(Node *x){
    while(x->l!=NIL){//找右子树最小节点
            x = x->l;
        }
        return x;
}
Node * Successor(Node *x){
    if(x->r!=NIL){
        return getMin(x->r);
    }
    Node *y = x->p;
    while(y!=NIL&&x==y->r){
        x=y;
        y = y->p;
    }
    return y;
}
void deletex(int key){
    Node *z = findx(root,key);//删除节点
    Node *y;//真正要删除的节点
    if(z->l==NIL||z->r==NIL){
        y = z;//没有或只有一个子节点时
    }else{

        y = Successor(z);//两个节点时
    }
    Node *x;//y的子节点
    if(y->l!=NIL){
        x = y->l;
    }else{
        x = y->r;
    }

    if(x!=NIL){
        x->p = y->p;
    }

    if(y->p == NIL){
        root = x;
    }else if(y->p->l == y){
        y->p->l = x;
    }else{
        y->p->r = x;
    }
    if(y!=z){
        z->key = y->key;
    }
}
int main()
{
    int n,key;
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s=="insert"){
            cin>>key;
            insert(key);
        }else if(s=="print"){
            inTW(root);
            cout<<endl;
            preTW(root);
            cout<<endl;
        }else if(s=="find"){
            cin>>key;
            Node *x = findx(root,key);
            if(x==NIL) cout<<"no"<<endl;
            else cout<<"yes"<<endl;
        }else if(s=="delete"){
            cin>>key;
            deletex(key);
        }
    }

    return 0;
}



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

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

    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }

    int now = A[0], ans = 0, cnt = 0;
    for(int i = 1; i < n; i++){
        if(now >= A[i]){
            cnt += 1;
            ans = max(ans, cnt);
            now = A[i];
        }else{
            ans = max(ans, cnt);
            cnt = 0;
            now = A[i];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int p[7][7][7];
int size[7][7];
int dx[]={1,0,0,1,1 ,1,1 ,0,0 ,1,1 ,1 ,1 };
int dy[]={0,1,0,1,-1,0,0 ,1,1 ,1,-1,1 ,-1};
int dz[]={0,0,1,0,0 ,1,-1,1,-1,1,1 ,-1,-1 };
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a){
		for(int i=0;i<7;i++)for(int j=0;j<7;j++){size[i][j]=0;for(int k=0;k<7;k++)p[i][j][k]=-1;}
		bool ok=false;
		for(int i=0;i<c;i++){
			int d,e;
			scanf("%d%d",&d,&e);
			if(ok)continue;
			e--;
			d--;
			p[d][e][size[d][e]++]=i%2;
			for(int j=0;j<a;j++){
				for(int k=0;k<a;k++){
					for(int l=0;l<a;l++){
						for(int m=0;m<13;m++){
							bool OK=true;
							for(int n=0;n<b;n++){
								if(0>j+n*dx[m]||a<=j+n*dx[m]||0>k+n*dy[m]||a<=k+n*dy[m]||0>l+n*dz[m]||a<=l+n*dz[m]||p[j+n*dx[m]][k+n*dy[m]][l+n*dz[m]]!=i%2)OK=false;
							}
							if(OK)ok=true;
							OK=true;
							for(int n=0;n<b;n++){
								if(0>j-n*dx[m]||a<=j-n*dx[m]||0>k-n*dy[m]||a<=k-n*dy[m]||0>l-n*dz[m]||a<=l-n*dz[m]||p[j-n*dx[m]][k-n*dy[m]][l-n*dz[m]]!=i%2)OK=false;
							}
							if(OK)ok=true;
						}
					}
				}
			}
			if(ok){
				if(i%2)printf("White %d\n",i+1);
				else printf("Black %d\n",i+1);
			}
		}
		if(!ok)printf("Draw\n");
	}
}

Measured memory_bytes: 1040
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define VI vector<int>
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
using namespace std;
VI g[100010];
int A[2];
int n;
int D[100010];
string ans[2] = {"Snuke", "Fennec"};
int bfs(){
	queue<int> q;
	q.push(1); q.push(n);
	for(int i = 2; i < n; i++){
		D[i] = -1;
	}
	D[1] = 0; D[n] = 1;
	while(!q.empty()){
		int cur = q.front(); q.pop();
		A[D[cur]&1]++;
		for(int i = 0; i < (int)g[cur].size(); i++){
			int j = g[cur][i];
			if(D[j] >= 0) continue;
			D[j] = D[cur] + 2;
			q.push(j);
		}
	}
	return A[0] > A[1];
}
int main(){
	scanf("%d", &n);
	int a, b;
	for(int i = 0; i < n - 1; i++){
		scanf("%d %d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	printf("%s\n", ans[bfs()].c_str());
	return 0;
}

Measured memory_bytes: 6272
from math import *
from sys import stdin,stdout
input=stdin.buffer.readline

ip=[int(x) for x in input().split()]
h1=ip[0]
m1=ip[1]
h2=ip[2]
m2=ip[3]
k=ip[4]

time=(h2*60+m2)-(h1*60+m1)-k
print(time)

Measured memory_bytes: 9212
#include                            <iostream>
#include                            <list>
#include                            <stdio.h>
#include                            <math.h>
#include                            <string.h>
#include                            <time.h>
#include                            <stdlib.h>
#include                            <string>
#include                            <bitset>
#include                            <vector>
#include                            <set>
#include                            <map>
#include                            <queue>
#include                            <algorithm>
#include                            <sstream>
#include                            <stack>
#include                            <iomanip>
#include                            <numeric>
#include                            <unordered_map>



using namespace                     std;
#define                             int long long int




signed main()
{
    int t = 1; //cin >> t;
    for (int test = 1; test <= t; test++)
    {
        int a, b, c, d; cin >> a >> b >> c >> d;
        vector<int> t = {a * c, a * d, b * c, b * d};
        sort(begin(t), end(t), greater<int>());
        cout << t.front();

        
    }
    return 0;
}

Measured memory_bytes: 3196
import numpy as np

N = int(input())
A = np.array(input().split(),dtype=np.int32)

def ord(n):
  cnt = 0
  while not n&1:
    n >>= 1
    cnt += 1
  return cnt

np_ord = np.frompyfunc(ord,1,1)
answer = np_ord(A).sum()
print(answer)

Measured memory_bytes: 22780
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
c,d=[],[]
for s,t in zip(a,b):
    if s<t:
        c.append(t-s)
    elif s>t:
        d.append(s-t)
c.sort()
d.sort(reverse=1)
i=0
j=0
f=0
while i<len(c) and j<len(d):
    if c[i]<=d[j]:
        d[j]-=c[i]
        i+=1
        f=1
    elif c[i]>d[j]:
        c[i]-=d[j]
        j+=1
if i<len(c):
    print(-1)
else:
    print(i+j+f)

Measured memory_bytes: 88520
package main

import (
  "fmt"
)

func main(){
  var c string
  fmt.Scan(&c)
  if c == "a" || c == "i" || c == "u" || c == "e" || c == "o" {
    fmt.Println("vowel")

  } else{
    fmt.Println("consonant")
  }
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    vector<int> xs;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        xs.push_back(a);
        xs.push_back(a + k);
    }
    sort(xs.begin(), xs.end());
    int largest = 0;
    for (int i = 0; i < 2 * n - 1; ++i) {
        largest = max(largest, xs[i + 1] - xs[i]);
    }
    cout << k - largest << endl;
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (i%2 == 1 && s[i] == 'R') {
      cout << "No" << endl; return 0;
    } else if (i%2 == 0 && s[i] == 'L') {
      cout << "No" << endl; return 0;
    }
  }
  cout << "Yes" << endl;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

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

    // N 人, M 箇所, 距離 L
    int N, M, L;
    cin >> N >> M >> L;
    // 休憩確率, 休憩時間, 速度
    vector<ld> P(N), T(N), V(N);
    for (int i = 0; i < N; i++)
    {
        cin >> P[i] >> T[i] >> V[i];
        P[i] /= 100;
    }
    // comb[i][j] := iCj
    ld comb[60][60];
    for (int i = 0; i <= 50; i++)
        comb[i][0] = 1.0;
    for (int i = 1; i <= 50; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
    // pn[i][j] := i 人目が j 回休憩する確率
    // tn[i][j] := i 人目が j 回休んだ時の所要時間 (L/V[i] + j*T)
    vector<vector<ld>> pn(N, vector<ld>(M + 1)), tn(N, vector<ld>(M + 1));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            tn[i][j] = ld(L) / V[i] + j * T[i];
            pn[i][j] = comb[M][j] * pow(P[i], j) * pow(1.0 - P[i], M - j);
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (abs(V[i]) < EPS)
        {
            cout << fixed << setprecision(10) << 0.0 << endl;
            continue;
        }
        ld res = 0;
        for (int j = 0; j <= M; j++)
        {
            ld p = pn[i][j];
            for (int k = 0; k < N; k++)
            {
                if (k == i)
                    continue;
                if (abs(V[i]) < EPS)
                    continue;
                ld sum = 0;
                for (int l = 0; l <= M; l++)
                {
                    if (tn[k][l] > tn[i][j] + EPS)
                        sum += pn[k][l];
                }
                p *= sum;
            }
            res += p;
        }
        cout << fixed << setprecision(10) << res << endl;
    }
}



Measured memory_bytes: 3656
import heapq
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))

q, k = map(int, input().split())
ds = [-1]*n
hq = [(0,k-1)]
while hq:
    c,idx = heapq.heappop(hq)
    if ds[idx] != -1:
        continue
    ds[idx] = c
    for i in g[idx]:
        if ds[i[0]] == -1:
            heapq.heappush(hq,(i[1]+c,i[0]))

for i in range(q):
    x, y = map(int, input().split())
    print(ds[x-1]+ds[y-1])

Measured memory_bytes: 50456
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
#define pint pair<int, int>
#define vint vector<int>
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;

int main(){
	int n; cin>>n;
	int a[100001];
	FOR(i,0,n) cin>>a[i];
	sort(a,a+n);
	ll ans=0;
	int m=INF;
	FOR(i,0,n/2){
		ans+=2*(a[n-1-i]-a[i]);
	}
	if(n%2==1){
		m=min(m,a[n/2+1]-a[n/2]);
		m=min(m,a[n/2]-a[n/2-1]);
	}else{
		m=min(m,a[n/2]-a[n/2-1]);
	}
	co(ans-m);
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>

using namespace std;

int main(int argc, char* argv[]) {
  long long N, A, B;
  cin >> N >> A >> B;

  if (A > B) {
    cout << 0 << endl;
    return 0;
  }

  if (A != B && N == 1) {
    cout << 0 << endl;
    return 0;
  }

  if (N == 2) {
    cout << 1 << endl;
    return 0;
  }

  long long n = N - 2;

  cout << n * B - n * A + 1 << endl;

  return 0;
}

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

int main(void){
    char str[5];
    scanf("%s", str);

    int i; //文字数。あとで使うのでiはここで定義
    for(i = 0; str[i] != '\0'; i++);//ヌルまで繰り返し
    
    if(i != 4 ){
        //printf("Sが４文字ではありません\n");
        exit(0);
    }

    for(int j = 0; j < 4; j++){
        if(str[j]<'A'||str[j]>'Z'){//アルファベット大文字ではない場合
            //printf("大文字ではありません\n");
            exit(0);
        }
    }
    //printf("S:%s\n", str);

    int point = 0;
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            //printf("%d,%d  " , str[i],str[j]);
            if(str[i]==str[j]) point++;
        }
    }
    //printf("\npoint:%d\n",point);
    if(point==8) printf("Yes\n");
    else printf("No\n");

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cmath>
#include<array>
#include<algorithm>
#include<queue>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
#include<map>
//#include<list>
#include<bitset>
#include<iomanip>

using namespace std;
using LLI = long long int;
LLI N;

//array<int, 8>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//array<int, 8>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//array<int, 4>dir_x2 = { 0,0,1,-1 };
//array<int, 4>dir_y2 = { 1,-1,0,0 };
//char alp[] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//LLI gcd(LLI x, LLI y) {
//	LLI  r;
//	if (x < y) {
//		swap(x, y);
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x, LLI y) {
//	return x / gcd(x, y) * y;
//}

//long nCr(int n, int r) {
//	long ans = 1;
//	for (int i = n; i > n - r; i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1; i++) {
//		ans = ans / i;
//	}
//	return ans;
//}
//long nHr(int n,int r) {
//	n = n + r - 1;
//	return nCr(n,r);
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//#define debug(x) cerr << #x << " : " << x << endl
//#define debugv(x) cerr << #x << " : "; for(auto i:x) cerr << i << ", "; cerr<<endl

int main(void) {
	LLI A, B, T;
	cin >> A >> B >> T;
	cout << (T / A) * B << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env ruby

sx, sy, tx, ty = gets.split.map(&:to_i)
tx -= sx
ty -= sy
res = "U" * ty + "R" * tx + "D" * ty + "L" * tx
res += "L" + "U" * (ty + 1) + "R" * (tx + 1) + "D"
res += "R" + "D" * (ty + 1) + "L" * (tx + 1) + "U"
puts res


Measured memory_bytes: 1916
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>
using namespace std;

int f(vector<int> v) {
	int res = 0;
	for (int i = 0; i < v.size(); i++) {
		// cout << i << " ";
		for (int j = i + 1; j < v.size(); j++) {
			if (v[i] > v[j]) res++;
		}
	}
	// cout << endl;
	return res;
}

void dfs(const vector<pair<int, int>>& vp1, 
	const vector<pair<int, int>>& vp2,
	int index1, int index2, int last,
	vector<int> seq, vector<int> v, int& res) {
	if (vp1.size() - index1 + vp2.size() - index2 + seq.size() < vp1.size())
		return;
	if (seq.size() == vp1.size()) {
		int r = f(seq);
		if (res == -1 || r < res)
			res = r;
		return;
	}

	if (res != -1) {
		int r = f(seq);
		if (r >= res) return;
	}

	if (seq.size() % 2 == 0) {
		while (index1 < vp1.size()) {
			if (vp1[index1].first >= last && v[vp1[index1].second] == 0) {
				seq.push_back(vp1[index1].second);
				v[vp1[index1].second] = 1;
				dfs(vp1, vp2, index1 + 1, index2, vp1[index1].first, seq, v, res);
				seq.pop_back();
				v[vp1[index1].second] = 0;
			}
			index1++;
		}
	}
	else {
		while (index2 < vp2.size()) {
			if (vp2[index2].first >= last && v[vp2[index2].second] == 0) {
				seq.push_back(vp2[index2].second);
				v[vp2[index2].second] = 1;
				dfs(vp1, vp2, index1, index2 + 1, vp2[index2].first, seq, v, res);
				seq.pop_back();
				v[vp2[index2].second] = 0;
			}
			index2++;
		}
	}
}

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<pair<int, int>> vp1, vp2;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (i % 2 == 0) 
			vp1.push_back(make_pair(a, i));
		else
			vp2.push_back(make_pair(a, i));
	}
	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		if (i % 2 == 0)
			vp2.push_back(make_pair(b, i));
		else
			vp1.push_back(make_pair(b, i));
	}

	sort(vp1.begin(), vp1.end());
	sort(vp2.begin(), vp2.end());
	int res = -1;
	int index1 = 0, index2 = 0;
	int last = 0;
	vector<int> seq;
	vector<int> v(n, 0);

	dfs(vp1, vp2, index1, index2, last, seq, v, res);
		
	cout << res << endl;
}









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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007


int main()
{
	int H, W, D, Q;
	cin >> H >> W >> D;
	int field[300][300];
	map<int, pair<int, int>> K;
	map<pair<int,int>, int> F;
	fx(H) {
		fy(W) {
			cin >> field[x][y];
			K[field[x][y]] = make_pair(x, y);
		}
	}
	int cost[10000];
	for (int i = 1; i <= D;i++) {
		cost[i] = 0;
		int j = i;
		while (j+D<=H*W) {
			pair<int, int> from = K[j];
			pair<int, int> to = K[j + D];
			cost[j+D] =cost[j] + abs(from.first - to.first) + abs(from.second - to.second);
			j += D;
		}
	}

	cin >> Q;

	fx(Q) {
		int l, r;
		cin >> l >> r;
		ce(cost[r]-cost[l])
	}

    return 0;
}



Measured memory_bytes: 7168
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    while(1){
        int n;
        cin>>n;
        if(n==0)break;
        int sum=0,s[n];
        for(int i=0;i<n;i++){
            cin>>s[i];
            sum+=s[i];
        }
        double m,a=0.0;
        m=double(sum)/double(n);
        for(int i=0;i<n;i++)a+=(double(s[i])-m)*(double(s[i])-m);
        cout<<sqrt(a/double(n))<<endl;
    }
    return 0;
}


Measured memory_bytes: 3232
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A: Traveling Budget
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int a, b, c, d;
  scanf("%d%d%d%d", &a, &b, &c, &d);
  printf("%d\n", min(a, b) + min(c, d));
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 300010
using namespace std;
typedef long long ll;
ll f[MAXN],f1[MAXN],f2[MAXN];
ll t[MAXN];
ll st[MAXN],q[MAXN];
ll sum[MAXN],tmp[MAXN];
int n,m;
void prepare(ll fx[]){
	fx[0]=0;
	int top=0;
	st[++top]=0;
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	for(ll i=1;i<=n;i++){
		fx[i]=fx[i-1];
		while(top>1&&q[st[top]]-q[st[top-1]]<=2ll*i*(st[top]-st[top-1]))
			top--;
		fx[i]=max(fx[i],fx[st[top]]+(i-st[top])*(i-st[top]+1)/2ll-sum[i]+sum[st[top]]);
		q[i]=i*i-i+2ll*(fx[i]+sum[i]);
		while(top>1&&(q[st[top]]-q[st[top-1]])*(i-st[top-1])<=(q[i]-q[st[top-1]])*(st[top]-st[top-1]))
			top--;
		st[++top]=i;
	}
}
void solve(ll f1[],ll f2[],ll l,ll r){
	if(l==r){
		f[l]=max(f[l],f1[l-1]+f2[l+1]-t[l]+1ll);
		return ;
	}
	int mid=(l+r)>>1,top=0;
	for(ll i=l-1;i<mid;i++){
		q[i]=i*i-i+2ll*(f1[i]+sum[i]);
		while(top>1&&(q[st[top]]-q[st[top-1]])*(i-st[top-1])<=(q[i]-q[st[top-1]])*(st[top]-st[top-1]))
			top--;
		st[++top]=i;
	}
	for(ll i=mid;i<=r;i++){
		while(top>1&&q[st[top]]-q[st[top-1]]<=2ll*i*(st[top]-st[top-1]))
			top--;
		tmp[i]=f1[st[top]]+f2[i+1]+(i-st[top])*(i-st[top]+1)/2ll-sum[i]+sum[st[top]];
	}
	for(int i=r-1;i>=mid;i--)
		tmp[i]=max(tmp[i],tmp[i+1]);
	for(int i=mid;i<=r;i++)
		f[i]=max(f[i],tmp[i]);
	solve(f1,f2,l,mid);
	solve(f1,f2,mid+1,r);
}
int main(){
	SF("%d",&n);
	for(int i=1;i<=n;i++){
		SF("%lld",&t[i]);
		f[i]=-t[i]+1ll;
	}
	prepare(f1);
	reverse(t+1,t+1+n);
	prepare(f2);
	reverse(t+1,t+1+n);
	reverse(f2+1,f2+1+n);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	solve(f1,f2,1,n);
	reverse(t+1,t+1+n);reverse(f1+1,f1+1+n),reverse(f2+1,f2+1+n);reverse(f+1,f+1+n);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+t[i];
	solve(f2,f1,1,n);
	reverse(t+1,t+1+n);reverse(f1+1,f1+1+n),reverse(f2+1,f2+1+n);reverse(f+1,f+1+n);
	SF("%d",&m);
	for(int i=1;i<=m;i++){
		int p;
		ll t1;
		SF("%d%lld",&p,&t1);
		PF("%lld\n",max(f1[p-1]+f2[p+1],f[p]+t[p]-t1));
	}
}

Measured memory_bytes: 21248
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define re register
#define ll long long
#define maxn 1e5+5
using namespace std;
ll n,a[3005],s;
int main()
{
	cin>>n;
	for(re int i=1;i<=n;i++)
		cin>>a[i],s+=a[i];
	s-=n;
	cout<<s;
}

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

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

  
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"

//region Template
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const int MOD = 1000000007;

using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;

#define finish(x) cout << x; exit(0);
#define fastIO cin.tie(0); cin.sync_with_stdio(false);

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }

//const string USCAO_TAG = "mountains";
void usaco(const string& USACO_TAG) { setIn(USACO_TAG + ".in"); setOut(USACO_TAG + ".out"); }
void print() {}
template<typename T, typename... Args>
void print(T firstArg, Args... args) {
	#ifdef LOCAL
	cout << firstArg << "\t";
	print(args...);
	#endif
}
//endregion

/* Notes:
 * Farah </3
 */

const int MAXN = 1e6 + 6;
const int INF = 2e9;


ll dp[MAXN];
ll pre[MAXN];

int main() {
	#ifdef LOCAL
	setIn("in.txt");
	setOut("out.txt");
	#endif

	ll n;
	cin >> n;

	dp[0] = 1;
	pre[0] = 1;
	for(int i = 1; i < n; i++){
		dp[i] = pre[i - 1] + 1;

		if(i > 1){
			dp[i] -= dp[i - 2];
			if(dp[i] < 0){
				dp[i] += MOD;
			}
		} else if(i == 1){
			dp[i] -= 1;
		}

		pre[i] = (pre[i - 1] + dp[i]) % MOD;
	}



	ll ans = (dp[n - 1] + (n - 1) * (n - 1) + 1) % MOD;
	for(int i = 1; i < n; i++){
		ans = (ans + dp[i - 1] * (i + (i < n - 1))) % MOD;
	}


	for(int i = 1; i < n - 1; i++){
		ans = (ans + ((dp[i - 1] * (n - 1)) % MOD) * (n - 1)) % MOD;
	}
	cout << ans - (n == 1) << endl;
}


Measured memory_bytes: 15872
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        int W = sc.nextInt();
        int H = sc.nextInt();
        
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();
        
        if((x -r < 0 || x + r > W)||(y-r<0 || y+r >H)){
             System.out.println("No");
        
        }
             else{
                  System.out.println("Yes");

             }
        }
}



Measured memory_bytes: 26212
package main

import (
	"fmt"
)

func main() {
  date := map[int]string{0:"SUN", 1:"MON", 2:"TUE", 3:"WED", 4:"THU", 5:"FRI", 6:"SAT"}
  var s string
  fmt.Scanf("%s", &s)
  
  ans := 0
  for k, v := range date {
    if v == s {
      ans = 7 - k
    }
  }
  fmt.Printf("%d\n", ans)
}

Measured memory_bytes: 1836
#include<stdio.h>


long long max(long long num1, long long num2)
{
    return (num1 > num2 ) ? num1 : num2;
}
int main()
{
   int  n,w,i,j,k;
    scanf("%d %d",&n,&w);
    int  wrr[n];
    long long vrr[n];
    for(k=0;k<n;k++)
    {
        scanf("%d %lld",&wrr[k],&vrr[k]);
    }

   long long T[n+1][w+1];
    for (i = 0; i <= n; i++)
     {
       for (j = 0; j <= w; j++)
       {
           if (i==0 || j==0)
               T[i][j] = 0;
           else if (wrr[i-1] <= j)
                 T[i][j] = max(vrr[i-1] + T[i-1][j-wrr[i-1]],  T[i-1][j]);
           else
                 T[i][j] = T[i-1][j];
       }
     }
  printf("%lld",T[n][w]);


    return 0;
}


Measured memory_bytes: 79104
#include <iostream>

long long x;

using namespace std;

long long c[400];

int main()
{
	cin >> x;
    for (long long i = 0; i <= 120; i++) c[i] = i * i * i * i * i;
	for (int a = 0; a <= 120; a++)
	for (int b = 0; b <= 120; b++)
	if (c[a] - c[b] == x) cout << a << " " << b, exit(0);
    for (int a = 0; a <= 120; a++)
	for (int b = 0; b <= 120; b++)
	if (c[a] + c[b] == x) cout << a << " " << -b, exit(0);
}


Measured memory_bytes: 3580
N = int(input())
fizzbuzz = []
for i in range(1, N + 1):
    if i % 15 == 0:
        continue
    elif i % 3 == 0:
        continue
    elif i % 5 == 0:
        continue
    else:
        fizzbuzz.append(i)
print(sum(fizzbuzz))

Measured memory_bytes: 29956
a = []
try:
    while True:
        x, y = map(float, input().split(","))
        a.append(complex(x, y))
except EOFError:
    pass
n = len(a)
ans = 0.0
p = a[0]
for i in range(n - 2):
    q, r = a[i + 1], a[i + 2]
    ans += (((q - p).conjugate() * (r - p)).imag) / 2
print(abs(ans))



Measured memory_bytes: 5592
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let n = read::<usize>();
    let vs = read_vec::<i32>();
    let costs = read_vec::<i32>();

    let mut ans = 0;
    for i in 0..n {
        let p = vs[i] - costs[i];
        if p > 0 {
            ans += p;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  string s,t;
  vector<string> u(200);
  vector<int> a;
  getline(cin, s);
  int j = 0;
  int n = s.size();
  rep(i,n){
    if(s.at(i) != ' '){
      u.at(j) += s.at(i);
    }
    else
    {
      j++;
    }
  }
  n = u.size();
  rep(i,n){
    string v = u.at(i);
    if(v.empty()) break;
    else if (v == "+" ){
      a.at(a.size()-2) = a.at(a.size()-2) + a.back();
      a.pop_back();
    }
    else if( v == "-"){
      a.at(a.size()-2) = a.at(a.size()-2) - a.back();
      a.pop_back();
    }
    else if( v == "*"){
      a.at(a.size()-2) = a.at(a.size()-2) * a.back();
      a.pop_back();
    }
    else{
      int x = std::stoi(v);
      a.push_back(x);
    }
  }
  cout << a.back() << endl;
}


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

using namespace std;

typedef long long int ll;
 
template<class T> inline bool chmax(T& a,T b){ if(a<b){ a=b; return true;} return false; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){ a=b; return true;} return false; }
 
typedef pair<int,int> pair;

int main(){
  int a,b,c;
  cin >> a >> b >> c;

  bool x=(a==b && a!=c);
  bool y=(b==c && a!=c);
  bool z=(a==c && a!=b);
  if(x || y || z) puts("Yes");
  else puts("No");
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9+7;
//const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

#ifdef DEBUG
#define OUTPUT(x) (output(x), output("\n"))
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

ll n;
vector<ll> line;
int main(){
	cin >> n;
	line.resize(n);
	foreach(i, line)cin>>i;
	map<int, int> m;
	m[-1] = 3;
	ll ans = 1;
	foreach(i, line){
		ans = ans * m[i-1] % MOD;
		--m[i-1];
		++m[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#define rep(i,x) for(int i = 0; i < x; i++)
typedef long long ll;
using namespace std;
const ll N = 1e9+7;

ll dev(ll x, ll y){
    ll ans = 0;
    ans = x / y;
    return ans;
}

ll gcd(ll m, ll n)
{
	ll temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}
int main(){
    ll a,b,c,d; cin >> a >> b >> c >> d;
    ll cd = gcd(c,d);
    ll cd2 = c*d/cd; 
    ll ans1 = dev(b,c) + dev(b,d) - dev(b,cd2);
    ll ans2 = dev(a-1,c) + dev(a-1,d) - dev(a-1,cd2);
    ll ans = (b - a + 1) - (ans1 - ans2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = list(str(input()))

used = [0]*1000

for i in range(1000):
  stri = str(i)
  if len(stri) == 2:
    stri = "0"+stri
  elif len(stri) == 1:
    stri = "00"+stri
  count = 0
  for j in range(N):
    if S[j] == stri[count]:
      count += 1
    if count == 3:
      used[i] = 1
      break

print(sum(used))

Measured memory_bytes: 42732
#include <iostream>
#include <string>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)

int main() {
    string s;
    while(cin>>s){
        REP(i,s.length()){
            if (s[i]!='@'){
                cout<<s[i];
            }else{
                i++;
                int x=s[i]-'0';
                i++;
                while(x--)cout<<s[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3152
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll mod(ll x){
  if(x>=0){return x%MOD;}
  x*=-1;x%=MOD;
  return (MOD-x)%MOD;
}
int main()
{
   ll n,k;
   cin>>n>>k;
   deque<ll>a;
   for(int i=0;i<n;i++){
	   ll b;cin>>b;
	   a.pb(b);
   }
   sort(all(a));
   ll ans=1;
   if(k%2)
   {
	   if(a[n-1] >= 0){ans = a[n-1];k--;a.pop_back();}
	   else{
		   for(int i=0;i<k;i++){ans*=a[n-i-1];ans = mod(ans);}
		   k=0;
	   }
	   
   }
   while(k)
   {
	   int x = a.size();
	   ll l = a[0]*a[1];
	   ll r = a[x-2]*a[x-1];
	   if(l >= r){
		   l = mod(l);
		   ans*=l;
		   a.pop_front();a.pop_front();
	   }
	   else{
	        r = mod(r);
		   ans*=r;
		   a.pop_back();a.pop_back();
	   }
	   k-=2;
	   ans = mod(ans);
   }
   cout<<ans;
}



Measured memory_bytes: 5216
#include<iostream>
 
using namespace std;
 
int main()
{
    char cup[4];
    int ans[4]={1,0,0,0};
    int i=0;
     
      while(cin >> cup[i])
    {
        i++;
        if(i==3)
        {
            int a;
            a=ans[cup[0]-'A'];
            ans[cup[0]-'A']=ans[cup[2]-'A'];
            ans[cup[2]-'A']=a;
            i=0;
        }
    }
    for(i=0;i<3;i++)
    {
        if(ans[i]==1)
        {
            char a;
            a='A'+i;
            cout << a << endl;
        }
    }
}

Measured memory_bytes: 1132
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

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

    if (a <= x && x <= a+b)
        cout << "YES" << endl;
    else 
        cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
  "fmt"
  "bufio"
  "os"
)

func main() {
  count := [2] int{0, 0}

  rd := bufio.NewReaderSize(os.Stdin, 100000)
  s := make([]byte, 0, 100000)
  for {
    l, p, _ := rd.ReadLine()
    s = append(s, l...)
    if !p {
      break
    }
  }

  n := len(s)

  for i := 0; i < n; i++ {
    if i % 2 == 0 {
      if s[i] == 48 {
        count[0]++
      } else {
        count[1]++
      }
    } else {
      if s[i] == 48 {
        count[1]++
      } else {
        count[0]++
      }
    }
  }

  if count[0] < count[1] {
    fmt.Println(count[0])
  } else {
    fmt.Println(count[1])
  }
}


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

int main()
{
    int m, n, i, j;
    vector<int> vec1, vec2;
    int o = 0;
    cin >> m;
    for (i=0;i<m;i++){
        cin >> n;
        vec1.push_back(n);
    }
    for (i=0;i<m;i++){
        cin >> n;
            if (vec1[i] > n){
                o = o + (vec1[i]-n);
            } 
    }
    cout << o;
    return 0;
}

Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static Scanner sc = new Scanner(System.in);
	static final long Mod = 1000_000_007L;
	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}

	void solve() {
		int N = nextInt();
		int A = nextInt();//here
		int B = nextInt();//here
		int AG = nextInt();//目的地
		int BG = nextInt();//目的地
		String S = next();
		//char[] cArray = S.toCharArray();
		String res = "No";

		if(N>1) {
			//移動範囲
			String tS = S.substring(Math.min(A, B), Math.max(AG,BG));
			//##が連続している場合達成不可能である
			if(tS.replace("##", "-").length()!=tS.length()) {
				out.println(res);
				return;
			}
		}

		boolean overtakef = false;
		//追い越す必要があるならtrue
		if(A < B && AG > BG || A > B && AG < BG) overtakef = true;
		if(overtakef) {
			String tS = S.substring(Math.max(A, B)-2, Math.min(AG,BG)+1);

			//out.println(tS.replace("...", "-")+" "+tS.length());
			//...が存在しない場合追い越すことができず達成不可能である
			if(tS.replace("...", "-").length()==tS.length()) {
				out.println(res);
				return;
			}
		}
		out.println("Yes");
	}
	private long max(long a, long b) {
		return Math.max(a, b);
	}
	private long min(long a, long b) {
		return Math.min(a, b);
	}
	private static int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)a[i] = nextInt();
		return a;
	}
	private static long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)a[i] = nextLong();
		return a;
	}
	private static int nextInt() {
		return Integer.parseInt(next());
	}
	private static long nextLong() {
		return Long.parseLong(next());
	}
	private static String next() {
		return sc.next();
	}
	static long gcd(long m,long n) {
		if (m<n) return gcd(n,m);
		if (n==0)return m;
		return gcd(n,m%n);
	}

}

/*
8 1 3 7 4
.#..#...
No

4 1 2 4 3
....
Yes

6 1 2 6 5
..#...
Yes
*/

Measured memory_bytes: 26568
package main

import (
	"fmt"
)

func main() {
	var n, ans string
	fmt.Scan(&n)

	for i := range n {
		if n[i:i+1] == "9" {
			ans += "1"
		} else {
			ans += "9"
		}
	}

	fmt.Println(ans)
}

Measured memory_bytes: 512
/*
ALDS1_4-A
??¶?´?
    n \leq 10,000
    q \leq 500
    0 \leq S???????´? \leq 10^9
    0 \leq T???????´? \leq 10^9
    T ???????´???????????????°??????
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUFSIZE 1000000
#define S_MAXSIZE 100000
#define Q_MAXSIZE 500

int sys_err(char *str);

int main(void)
{
  FILE *fh;
  int i;
  int j;
  int s[S_MAXSIZE];
  int t[Q_MAXSIZE];
  int n;
  int q;
  int ans = 0;
  int x;

  /*  if ((fh = fopen("/home/muz/Downloads/ALDS1_4_A_in8.txt", "r")) == NULL) {
    sys_err("fopen");
  }
  */
  fh = stdin;

  fscanf(fh, "%d", &n);
  for (i=0; i<n; i++){
    fscanf(fh, "%d", &x);
    s[i] = x;
  }

  fscanf(fh, "%d", &q);
  for (i=0; i<q; i++){
    fscanf(fh, "%d", &x);
    t[i] = x;
  }

  for (i=0; i<q; i++){
    for (j=0; j<n; j++){
      if (s[j] == t[i]){
	ans+=1;
	break;
      }
    }
  }

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

  exit(0);
}

int sys_err(char *str)
{
  fputs(str, stderr);
  exit(0);

  return(0);
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(N);
  
  for (int i=0; i<N; i++) {
    cin >> A[i] >> B[i];
  }
  
  vector<pair<int,int>> AB(N);
  for (int i=0; i<N; i++) {
    AB[i] = make_pair(A[i],B[i]);
  }
  
  sort(AB.begin(), AB.end());
  
  long long ans = 0;
  for (int i=0; i<N; i++) {
    int buy = min(M, AB[i].second);
    
    ans += (long long)buy * AB[i].first;
    
    M -= buy;
  }
  
  cout << ans << endl;
  
  
  
}

Measured memory_bytes: 1792