akhauriyash/Code-Regression huggingface dataset:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = (int) 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

void precalc() {
}


const int maxn = (int) 1e5 + 10;
long long a[maxn];

int q;

int n;


int n00;

int read() {
  if (scanf("%lld%d", a, &q) < 1) {
    return 0;
  }
  n00 = a[0];

  n = 1;
  for (int i = 0; i < q; ++i) {
    long long x;
    scanf("%lld", &x);
    while (n && a[n - 1] >= x) {
      --n;
    }

    a[n++] = x;
  }
  return 1;
}

long long ans[maxn];

void solve() {
  int n0 = a[0];

  for (int i = 0; i < n00; ++i) {
    ans[i] = 0;
  }

  map<long long, long long> bs;
  bs[a[n - 1]] = 1;

  int pos = n - 1;
  while (sz(bs)) {
    auto iter = bs.end();
    --iter;
    long long x = iter->first;

    if (x <= n0) {
      for (auto p : bs) {
        ans[p.first - 1] += p.second;
      }
      break;
    }

    long long bal = iter->second;
    //eprintf("got %lld with %lld\n", x, bal);
    bs.erase(iter);

    while (pos >= 0 && a[pos] >= x) {
      --pos;
    }
    assert(pos >= 0);
    long long nx = a[pos];
    //eprintf("x = %lld, nx = %lld\n", x, nx);

    bs[nx] += (x / nx) * bal;
    x %= nx;

    bs[x] += bal;
  }

  for (int i = n0 - 1; i; --i) {
    ans[i - 1] += ans[i];
  }

  for (int i = 0; i < n00; ++i) {
    printf("%lld\n", ans[i]);
  }
  assert(accumulate(ans, ans + n00, 0ll) == a[n - 1]);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int M=1000000007;
int k,n,m,p,x;
int d[N],cnt[N],Ans;
vector<int>g[N];
deque<int>f[N][3];
inline void Add(int& x,int y){
	x=(x+y)%M;
}
void Dfs(int x,int y){
	m=max(m,y);cnt[y]++;
	int mx=0;
	for(int k=0;k<g[x].size();k++){
		int v=g[x][k];
		Dfs(v,y+1);
		if(f[x][0].size()<f[v][0].size())
			for(int i=0;i<3;i++)swap(f[x][i],f[v][i]);
		int m=f[v][0].size();mx=max(mx,m);
		for(int i=0;i<m;i++){
			int tmp[3]={0,0,0},s=0,t=0;
			for(int j=0;j<3;j++)Add(s,f[x][j][i]),Add(t,f[v][j][i]);
			tmp[0]=1ll*f[x][0][i]*f[v][0][i]%M;
			Add(tmp[1],1ll*f[x][0][i]*f[v][1][i]%M);
			Add(tmp[1],1ll*f[x][1][i]*f[v][0][i]%M);
			tmp[2]=1ll*s*t%M;
			Add(tmp[2],M-tmp[0]);Add(tmp[2],M-tmp[1]);
			for(int j=0;j<3;j++)f[x][j][i]=tmp[j];
		}
		for(int i=0;i<3;i++){
			deque<int>tmp;f[v][i].swap(tmp);
		}
	}
	f[x][0].push_front(1);f[x][1].push_front(1);f[x][2].push_front(0);
	for(int i=0;i<=mx;i++)Add(f[x][0][i],f[x][2][i]),f[x][2][i]=0;
}
inline int Pow(int x,int y){
	int Ans=1;
	for(;y;y>>=1,x=1ll*x*x%M)if(y&1)Ans=1ll*Ans*x%M;
	return Ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&x),g[x].push_back(i);
	Dfs(0,0);
	for(int i=0;i<=m;i++)Add(Ans,1ll*f[0][1][i]*Pow(2,n+1-cnt[i])%M);
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 498816
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <stdexcept>
using namespace std;

int main() {
  string S;
  cin >> S;
  cout << (S <= "2019/04/30" ? "Heisei" : "TBD") << endl;
  return 0;	 
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,m;
    cin >> n >> m;
    vector<vector<ll>> mod(m);
    for(i = 0;i < n;++i){
        ll x;
        cin >> x;
        mod.at(x%m).push_back(x);
    }
    ll ans = mod.at(0).size()/2;
    if(m%2 == 0){
        ans += mod.at(m/2).size()/2;
        for(i = 1;i < m/2;++i){
            if(mod.at(i).size() == mod.at(m-i).size()){
                ans += mod.at(i).size();
                continue;
            }
            ll ind;
            if(mod.at(i).size() < mod.at(m-i).size()) ind = m-i;
            else ind = i;
            ll plus = mod.at(m - ind).size();
            ll spare = mod.at(ind).size() - mod.at(m - ind).size();
            ll even = 0, odd = 0;
            sort(all(mod.at(ind)));
            ll tmp = mod.at(ind).at(0);
            ll cnt = 1;
            for(j = 1;j < mod.at(ind).size();++j){
                if(tmp == mod.at(ind).at(j)) ++cnt;
                else{
                    odd += cnt%2; even += cnt - cnt%2;
                    tmp = mod.at(ind).at(j);
                    cnt = 1;
                }
            }
            odd += cnt%2; even += cnt - cnt%2;
            ans += plus;
            if(spare >= even) ans += even/2;
            else{
                ans += (even - (plus - odd))/2;
            }
        }
    }else{
        for(i = 1;i <= (m-1)/2;++i){
            if(mod.at(i).size() == mod.at(m-i).size()){
                ans += mod.at(i).size();
                continue;
            }
            ll ind;
            if(mod.at(i).size() < mod.at(m-i).size()) ind = m-i;
            else ind = i;
            ll plus = mod.at(m - ind).size();
            ll spare = mod.at(ind).size() - mod.at(m - ind).size();
            ll even = 0, odd = 0;
            sort(all(mod.at(ind)));
            ll tmp = mod.at(ind).at(0);
            ll cnt = 1;
            for(j = 1;j < mod.at(ind).size();++j){
                if(tmp == mod.at(ind).at(j)) ++cnt;
                else{
                    odd += cnt%2; even += cnt - cnt%2;
                    tmp = mod.at(ind).at(j);
                    cnt = 1;
                }
            }
            odd += cnt%2; even += cnt - cnt%2;
            ans += plus;
            if(spare >= even) ans += even/2;
            else{
                ans += (even - (plus - odd))/2;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 8720
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int MAX_V = 300;
const int INF = (1 << 28);

struct edge {
	int to, cap, rev;
	edge(const int &_to, const int &_cap, const int &_rev) :to(_to), cap(_cap), rev(_rev) {}
};//to????????????cap???????????????????????????????§??????¨??????????????¢????????????G[to][rev]???????´?????????????????????¨????????????

vector<edge> G[MAX_V];	//?§????s,??????t??¨???????????§???????±???????????????¢???????????°????????¨????????£??\???????????§??¨???
vector<int> level(MAX_V);	//????????????s??????????????¢
vector<int> iter(MAX_V);	//???????????§?????§????????????????????£??????

							//from??????to??????????????????cap???????????°?????????????????????
void add_edge(const int &from, const int &to, const int &cap) {
	G[from].emplace_back(to, cap, G[to].size());
	G[to].emplace_back(from, 0, G[from].size() - 1);
}


//s????????????????????¢???BFS??§?±???????
void bfs(const int &s) {
	fill(level.begin(), level.end(), -1);
	queue<int> que;
	level[s] = 0;
	que.emplace(s);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i = 0; i < G[v].size(); ++i) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.emplace(e.to);
			}
		}
	}
}

//?¢?????????????DFS??§??¢???
int dfs(const int &v, const int& t, const int& f) {
	if (v == t)return f;
	for (int &i = iter[v]; i < G[v].size(); ++i) {
		edge &e = G[v][i];
		if (e.cap > 0 && level[v] < level[e.to]) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(const int &s, const int& t) {
	int flow = 0;
	while (true) {
		bfs(s);
		if (level[t] < 0)return flow;	//s??????t????????????????????¨????????????????????????????????¨?????§???????????´??????0?????????
		fill(iter.begin(), iter.end(), 0);
		int f;
		while ((f = dfs(s, t, INF))>0) {
			flow += f;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::ios_base::sync_with_stdio(false);
	int V, E,s,t,c; cin >> V >> E;
	for (int i = 0; i < E; ++i) {
		cin >> s >> t >> c;
		add_edge(s, t, c);
	}
	cout << max_flow(0, V - 1)<<endl;
}

Measured memory_bytes: 1264
#include <stdio.h>



#define N 100000
#define Q 50000



void display(int data[], int n);

void bubbleSort(int data[], int n);
void selectionSort(int data[], int n);
void insertionSort(int data[], int n);

int binarySearchTF(int key, int data[], int n);



int main(){
	
	//??????
	int data[N];
	
	int S[N];
	int T[Q];
	
	
	//??其?????即?????属
	int i, k;
	
	//?????????????卒???属
	int n, q;
	
	//?????属, ?????属??????
	int count = 0;
	
	
	//????卒???属?????\???
	scanf("%d", &n);	
	
	//??????????????\???
	for(i=0; i<n; i++){
		
		scanf("%d", &S[i]);
		
	}
	
	scanf("%d", &q);
	
	for(i=0; i<q; i++){
		
		scanf("%d", &T[i]);
		
	}
	
	
	//insertionSort(S, n);
	
	for(i=0; i<q; i++){
		
		if(binarySearchTF(T[i], S, n)){
			
			count++;
			
		}
		
	}
	
	printf("%d\n", count);
	
	return 0;
	
}



//?????????????卒???????????????????
void display(int data[], int n){
	
	int i;
	
	for(i=0; i<n; i++){
		if(i>0){
			printf(" ");
		}
		printf("%d", data[i]);
	}
	
	printf("\n");
	
	return;
}



//??????????????????
void bubbleSort(int data[], int n){
	
	int i, j, temp;
	int count = 0;
	
	for(i=0; i<n; i++){
		
		for(j=n-1; j>i; j--){
			
			if(data[j] < data[j-1]){
				
				temp = data[j];
				data[j] = data[j-1];
				data[j-1] = temp;
				
				//?????属????即????
				count++;
				
			}
			
		}
		
		//???????????其????????????
		//display(data, n);
		
	}
	
	
	//??????
	//display(data, n);
	
	//???????????属?????????
	//printf("%d\n", count);
	
	return;
}



//???????????????
void selectionSort(int data[], int n){
	
	int i, k, temp;
	int min = 0;
	int count = 0;
	
	for(i=0; i<n; i++){
		
		min = i;
		
		for(k=i+1; k<n; k++){
			
			if(data[min] > data[k]){
				
				min = k;
				
			}
			
		}
		
		
		//min > i  ???  ??????????????????
		if(min > i){
			
			temp = data[min];
			data[min] = data[i];
			data[i] = temp;
			
			count++;
		}
		
	}
	
	display(data, n);
	
	//???????????属?????????
	//printf("%d\n", count);
	
	return;
}



//?????\?????????
void insertionSort(int data[], int n){
	
	int i, j, temp;
	
	for(i=1; i<n; i++){
		
		j = i;
		temp = data[j];
		
		while(j>0 && temp < data[j-1]){
			
			data[j] = data[j-1];
			j--;
			
		}
		data[j] = temp;
		
		//???????????其????????????
		//display(data, n);
	}
	
	return;
}



//????????蔵?卒蔵	??????????????????(0 or 1)?????????
int binarySearchTF(int key, int data[], int n){
	
	int min = 0,  max = n-1, pos = (min+max)/2;
	
	while(min <= max){
		
		if(key < data[pos]){
			
			max = pos-1;
			pos = (min+max)/2;
			
		}
		else if(key > data[pos]){
			
			min = pos+1;
			pos = (min+max)/2;
			
		}
		else{
			
			return 1;
			
		}
		
	}
	
	return 0;
	
}

Measured memory_bytes: 1184
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int K = sc.nextInt();
    
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= M; j++) {
        if (M*i + N*j - i*j*2 == K) {
          System.out.println("Yes");
          return;
        }
      }
    }
    System.out.println("No");
  }
}

Measured memory_bytes: 21972
digits :: Int -> Int -> Int
digits n a
    | a == 0    = n
    | otherwise = digits (n + 1)  (a `div` 10)

ans :: (Int,Int) -> Int
ans (a,b) = digits 0 (a + b)

main = do
  c <- getContents
  let i = map (map read . words) $ lines c :: [[Int]]
      j = map (\(x0:x1:xs) -> (x0,x1)) i
      k = map ans j
  mapM_ (putStrLn.show) k

Measured memory_bytes: 4096
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;
int main(){
  long n,m,ii;
  vector<long> l,r;

  cin >> n >> m;
  l.resize(m);
  r.resize(m);

  for(ii=0;ii<m;ii++){
    cin >> l[ii] >> r[ii];
  }
  long min = 0,max = LONG_MAX;
  for(ii=0;ii<m;ii++){
    if(l[ii] > min){
      min = l[ii];
    }
    if(r[ii] < max){
      max = r[ii];
    }
  }
  long ret;
  ret = max - min + 1;
  if(ret < 0){
    ret = 0;
  }
  cout << ret << endl;
  
  return 0;
}


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

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

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

  int ans;
  if (a >= 10 || b >= 10)
    ans = -1;
  else
    ans = a * b;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a,b;
    char c;
    scanf("%d %c %d",&a,&c,&b);
    if(c=='+'){
        printf("%d",a+b);
    }
    else if(c=='-'){
        printf("%d",a-b);
    }


    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cctype>

using namespace std;

int main() {
        string a, b, c;
        cin >> a >> b >> c;
        char aa, bb, cc;
        aa = toupper(a[0]);
        bb = toupper(b[0]);
        cc = toupper(c[0]);
        cout << aa << bb << cc << endl;
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <fstream>
using namespace std;
typedef long long ll;

int main()
{
	int A = 0, B = 0, a, b;
	for(int i = 0; i < 4; i++){
		cin>>a;
		A += a;
	}
	for(int i = 0; i < 4; i++){
		cin>>b;
		B += b;
	}
	cout<<max(A, B)<<endl;
	//cin.sync(); cin.get();
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
string s,t;
int main(){
  cin>>s>>t;
  int n=s.size(),m=t.size();
  int dp[n+1][m+1];
  memset(dp,0,sizeof dp);
  string lcs[n+1][m+1];
  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
      lcs[i][j]="";
  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++){
      if(i==0 || j==0) continue;
      else if(s[i-1]==t[j-1]) dp[i][j]=1+dp[i-1][j-1];
      else if(s[i-1]!=t[j-1]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      
    }
  int len=dp[n][m];
  string p="";
  int i=n,j=m;
  while(i>0 && j>0 && len>0){
    if(s[i-1]==t[j-1]) {p=s[i-1]+p;i--;j--;len--;}
    else{
      if(dp[i-1][j]>dp[i][j-1]) i--;
      else j--;
    }
  }
  cout<<p;
  
}

Measured memory_bytes: 105856
char s[65536],t[65536];
int n,i,r,w,c;
int main()
{
	for(;scanf("%d",&n),n;puts(s)){
		scanf("%s",s);
		for(i=0;i++<n;t[w]=0,strcpy(s,t)){
			for(r=w=0;r<strlen(s);t[w++]=s[r],r+=c){
				for(c=0;s[r+c]==s[r];++c);
				for(sprintf(t+w,"%d\0",c);t[++w];);
			}
		}
	}
	exit(0);
}

Measured memory_bytes: 500
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

static const int N = 1000;

int lcs(string X, string Y) {
	int c[N + 1][N + 1];
	int m = X.size();
	int n = Y.size();
	int maxl = 0;
	X = ' ' + X;
	Y = ' ' + Y;
	for (int i = 0; i <= m; i++) c[i][0] = 0;
	for (int j = 1; j <= n; j++) c[0][j] = 0;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (X[i] == Y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else {
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
			maxl = max(maxl, c[i][j]);
		}	
	}

	return maxl;
}

int main() {
	string s1, s2;
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2) << endl;
	}
	return 0;
}



Measured memory_bytes: 7088
#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <sys/timeb.h>
#include <cstdio>
#include <sys/time.h>

using namespace std;
#define ll long long
#define uint unsigned int
#define ulong unsigned long long int

template<typename T> bool InRange(T t, T l, T r){ return l <= t && t < r; }

int main(){
	
	int A,B;
	int K;
	cin >> A >> B >> K;
	
	vector<int> v;
	for(int i=0;i<K;i++){
		if(A + i > B) break;
		v.push_back(A + i);
	}
	for(int i=0;i<K;i++){
		if(B - i < A) break;
		v.push_back(B - i);
	}
	
	sort(v.begin(), v.end());
	auto vu = unique(v.begin(), v.end());
	//cout << (int) (vu - v.begin()) << endl;
	for(auto n = v.begin(); n < vu; n++) cout << *n << endl;
	
    return 0;
}

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

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

template<typename T>
void cmpmax(T* reference, T value) {
	*reference = max(*reference, value);
}

template<typename T>
void cmpmin(T* reference, T value) {
	*reference = min(*reference, value);
}

const ll mod = 998244353;

static const ll INF = 1e15;


int main() {
	int n;
	cin >> n;
	vector<int> cs(4,0);
	rep(i, n) {
		int a;
		cin >> a;
		cs[a]++;
	}
	vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(n + 1, vector<double>(n + 1, 0)));
	for (int k = 0; k <= n; k++) {
		for (int j = 0; j <= n; j++) {
			for (int i = 0; i <= n; i++) {
				if (i == 0 && j == 0 && k == 0) continue;
				if (i + j + k > n) continue;
				double left = i + j + k;
				double right = 0;
				if (i) {
					right += i * dp[i - 1][j][k];
				}
				if (j && i+1<=n) {
					right += j * dp[i + 1][j - 1][k];
				}
				if (k && j + 1 <= n) {
					right += k * dp[i][j + 1][k-1];
				}
				right += n;
				dp[i][j][k] = right / (i + j + k);
			}
		}
	}
	cout << fixed << setprecision(10);
	cout << dp[cs[1]][cs[2]][cs[3]] << endl;
	return 0;
}
	

Measured memory_bytes: 216960
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main(){
  string red,gre;
  string ans,out;
  queue<char> quer,queg;
  
  char c;
  int i,n,m;
  while(cin>>red){
    if(red=="-") break;
    cin>>gre>>out;
    m=gre.size()+red.size()-out.size();
    for(i=0;i<red.size();i++) quer.push(red[i]);
    for(i=0;i<gre.size();i++) queg.push(gre[i]);
    n=0;
    c=queg.front();
    queg.pop();
    ans.clear();
    while(!quer.empty()||!queg.empty()){
      //cout<<":"<<c<<endl;
      if(out[n]==c){
        c=quer.front();
        quer.pop();
        n++;
      }
      else{
        ans+=c;
        c=queg.front();
        queg.pop();
      }
    }
    if(ans.size()!=m) ans+=c;
    cout<<ans<<endl;
  }
  return 0;
}

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

int main() {
  int n, k, i, j, a = 1000000009;
  cin >> n >> k;
  
  vector<int> h(n), x(n);
  for(i = 0; i < n; i++){
    cin >> h.at(i);
  }
  
  for(i = 1; i < n; i++){
    for(j = max(0, i - k); j < i; j++){
      a = min(a, x.at(j) + abs(h.at(j) - h.at(i)));
    }
    x.at(i) = a;
    a = 1000000009;
  }
  
  cout << x.at(n - 1) << endl;
}

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

int main() {
    int N, M, R, ans = 1e9;
    cin >> N >> M >> R;
    vector<vector<int>> dist(N, vector<int>(N, 1e9));
    vector<int> r(R);
    for(int i = 0; i < R; ++i) {
        cin >> r[i];
        --r[i];
    }
    for(int i = 0; i < M; ++i) {
        int A, B, C;
        cin >> A >> B >> C;
        --A, --B;
        dist[A][B] = dist[B][A] = C;
    }
    for(int k = 0; k < N; ++k)
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    sort(r.begin(), r.end());
    do {
        int tmp = 0;
        for(int i = 1; i < R; ++i)
            tmp += dist[r[i - 1]][r[i]];
        ans = min(ans, tmp);
    } while(next_permutation(r.begin(), r.end()));

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'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'};
char moji2[26]={'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'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int n;
    cin >> n;
    int A[n];
    int su = 0;
    REP(i,n){
        cin >> A[i];
        su += A[i];
    }
    int sousa;
    int wa = n * (n + 1) / 2;
    if( su % wa != 0){
        cout << "NO" << endl;
        return 0;
    }

    sousa = su / wa;




    int ju = 0;
    REP(i,n){
        int sa = A[(i + 1) % n] - A[i];
        if( (sa > sousa) or ((sousa - sa) % n != 0)){
            cout << "NO" << endl;
            return 0;
        }
        ju += (sousa - sa) / n;
    }
    if(ju != sousa){
        cout << "NO" << endl;
    }
    else cout <<"YES" << endl;

}

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

struct piece{
  int w,d,S;
  bool operator<(const piece &a)const{
    return this->S<a.S;
  }
};

void renewPiece(int w,int d,piece* p){
  p->w=w;
  p->d=d;
  p->S=w*d;
}


int main(){
  int n,w,d;
  while(cin>>n>>w>>d){
    if(w==0)return 0;
    vector<piece> P;
    piece tmp;
    renewPiece(w,d,&tmp);
    P.push_back(tmp);
    int p,s;
    piece a,b;
    for(int i=0;i<n;i++){
      cin>>p>>s;
      p--;
      s = s % (2*P[p].w+2*P[p].d);
      if(s>2*P[p].w+P[p].d || (s < P[p].d + P[p].w && s > P[p].w)){

	if(s>2*P[p].w+P[p].d){
	  s-=2*P[p].w + P[p].d;
	}else{
	  s-=P[p].w;
	}
	renewPiece(P[p].w,P[p].d-s,&a);
	renewPiece(P[p].w,s,&b);

      }else{
	if(s>P[p].d+P[p].w){
	  s-=P[p].d+P[p].w;
	}

	renewPiece(P[p].w-s,P[p].d,&a);
	renewPiece(s,P[p].d,&b);
      }

      if(a.S<b.S){
	piece tmp = b;
	b = a;
	a = tmp;
      }

      P.erase(P.begin() + p);
      P.push_back(b);
      P.push_back(a);
    }
    sort(P.begin(), P.end());
    for(int i=0;i<P.size()-1;i++){
      cout << P[i].S << " ";
    }
    cout << P[P.size()-1].S<< endl;
  }
}

Measured memory_bytes: 1224
import numpy as np

count = 0
N,M,C = [int(i) for i in input().split(" ")]
B = [int(i) for i in input().split()]
B = np.array(B)
A = [list(map(int, input().split())) for _ in range(N)]
A = np.array(A)
for a in A:
  if np.dot(a,B) + C > 0:
    count += 1
print(count)

Measured memory_bytes: 12428
mod = 1000000007

N,K = map(int, input().split(sep=" "))
#選ぶ個数が違えば絶対その和は違うだろう
sum = 0
for i in range(K,N+2,1):
    Min = (((i+1)*i)/2)%mod
    Max = (i*(N+2)-((i+1)*i)/2)%mod
    sum = (sum + Max - Min +1)%mod 
print(int(sum))

Measured memory_bytes: 9196
#include <iostream>

using namespace std;

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);

    int counter=2,cur=a;
    if( b == 1){
        printf("0");
        return 0;
    }

    while(cur < b){
        cur += a-1;
        counter ++;
    }

    printf("%d",counter-1);

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

// Manages Union-Find Forest.
class UnionFindForest {
  std::vector<int> parent_;
  std::vector<int> rank_;
  std::vector<int> size_;

public:
  // Initialize forest.
  // parent_[i]=i, rank_[i]=0, size_[i]=1.
  UnionFindForest(const int &n);
  // Get the number of the root of the node q.
  int Root(const int &q);
  // Return true if the roots of x and y is same.
  bool IsSame(const int &x, const int &y);
  // Unite the tree x and tree y.
  void Unite(int x, int y);
  // Get the number of nodes which are the same group as node q.
  int Size(const int &q);
};
UnionFindForest::UnionFindForest(const int &n) {
  parent_.resize(n);
  rank_.resize(n);
  size_.resize(n);
  for (int i = 0; i < n; i++) {
    parent_[i] = i;
    rank_[i]   = 0;
    size_[i]   = 1;
  }
}
int UnionFindForest::Size(const int &q) {
  return size_[Root(q)];
}

int UnionFindForest::Root(const int &q) {
  if (parent_[q] == q) {
    return q;
  } else {
    return parent_[q] = Root(parent_[q]);
  }
}

bool UnionFindForest::IsSame(const int &x, const int &y) {
  return Root(x) == Root(y);
}

void UnionFindForest::Unite(int x, int y) {
  x = Root(x);
  y = Root(y);
  if (x == y) return;
  if (rank_[x] < rank_[y]) {
    parent_[x] = y;
    size_[y] += size_[x];
    size_[x] = 0;

  } else {
    parent_[y] = x;
    size_[x] += size_[y];
    size_[y] = 0;
    if (rank_[x] == rank_[y]) rank_[x]++;
  }
}

int main(void){
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int h,w;
  cin>>h>>w;
  // std::map<std::pair<int,int>,int> node_hash;
  // std::map<int,std::pair<int,int>> map_hash;
  char map[410][410];
  for(int c=0;c<=w+1;c++){
    map[0][c]='@';
    map[h+1][c]='@';
  }
  for(int r=1;r<=h;r++){
    map[r][0]='@';
    std::string s;
    cin>>s;
    for(int c=1;c<=w;c++){
      map[r][c]=s[c-1];
    }
    map[r][w+1]='@';
  }

  // int node_num=0;
  // for(int r=1;r<=h;r++){
  //   for(int c=1;c<=w;c++){
  //     node_hash[std::make_pair(r,c)]=node_num;
  //     map_hash[node_num]=std::make_pair(r,c);
  //     node_num++;
  //
  //   }
  // }

  UnionFindForest uf(h*w+10);

  for(int r=1;r<=h;r++){
    for(int c=1;c<=w;c++){
      for(int vr=-1;vr<=1;vr++){
        for(int vc=-1;vc<=1;vc++){
          if((vr==0&&vc!=0)||(vr!=0&&vc==0)){

            if(map[r+vr][c+vc]!='@'&&map[r][c]!=map[r+vr][c+vc]){
              uf.Unite((r-1)*w+c-1,(r+vr-1)*w+c+vc-1);
            }

          }
        }
      }
    }
  }




  int64_t result=0;
  int64_t w_count[161000]={},b_count[161000]={};
  for(int node=0;node<h*w;node++){
    if(map[node/w+1][node%w+1]=='#'){
      b_count[uf.Root(node)]++;
    }else{
      w_count[uf.Root(node)]++;
    }
  }

  for(int i=0;i<h*w;i++){
    result+=b_count[i]*w_count[i];
  }

  cout<<result<<endl;

  
  return 0;
}


Measured memory_bytes: 4864
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
	int n,k;
	cin >> n >>k;
	int arr[n],dp[n+1]={0};
	
	for (int i=0;i<n;++i)
	cin >> arr[i];
	
	dp[0]=0;
	dp[1]= abs(arr[1]-arr[0]);
	
	for (int i=2;i<n;++i)
	{
	   dp[i]=2e9;
	  for (int j=1;j<= min(i,k);++j)
	  {
		dp[i] = min(dp[i-j]+abs(arr[i]-arr[i-j]), dp[i]);
	  }
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int x;
        int i=1;
        while(true){
            x=sc.nextInt();
            if(x==0)break;
            System.out.println("Case"+" "+i+":"+" "+x);
            i++;
        }
    }
}

Measured memory_bytes: 32972
#include <stdio.h>
#include <string.h>
int main ()
{
	int c=0;
	char s[101];
	scanf("%s",&s);
	for(int i=0;i<strlen(s)/2;i++)
	{
		if(s[i]!=s[strlen(s)-i-1])
		{
			c++;
		}
	}
	printf("%i",c);
	return 0;
}


Measured memory_bytes: 128
N = int(input())
num_lis = list(map(int,input().split()))

num_lis.sort(reverse = True)
total = 0
for n in range(N):
    if n < (N-1):
        total += num_lis[n] * (1/2)**(n+1)
    else:
        total += num_lis[n] * (1/2)**(n)
print(total)

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list(int(input()) for i in range(n))

cnt = 0
for i in range(n):
    if a[i]%2==1:cnt+=1

if cnt>0:
    print('first')
else:
    print('second')


Measured memory_bytes: 7084
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <vector>
using namespace std;


struct Node {
    int key;
    Node *parent;		// ???
    Node *left;			// ?????????
    Node *right;		// ?????????
};

Node *root, *NIL;

void insert( int k );

void PreOrder( Node *node );

void InOrder( Node *node );


int main()
{
    int n;

    scanf("%d", &n);
    
    for ( int i = 0; i < n; i++ ) {
	char str[100];
	scanf("%s", str);
	if ( !strcmp( str, "insert" ) ) {
	    int d;
	    scanf("%d", &d);
	    insert( d );
	}
	else if ( !strcmp( str, "print" ) ) {
	    InOrder( root );
	    printf("\n");

	    PreOrder( root );
	    printf("\n");
	}
    }

    return 0;
}




void insert( int k )
{
    Node *p_y = NIL;		// ?????¨??????????????????????£?????¨??????????
    Node *p_x = root;
    
    Node *p_z = (Node *)malloc( sizeof( Node ) );
    p_z->parent = NIL;
    p_z->left   = NIL;
    p_z->right  = NIL;
    p_z->key    = k;

    while ( p_x != NULL ) {
	p_y = p_x;
	if ( k < p_x->key ) { // ???
	    p_x = p_x->left;
	}
	else {
	    p_x = p_x->right;
	}
    }

    p_z->parent = p_y;

    if ( p_y == NULL ) {
	root = p_z;
    }
    else if ( p_z->key < p_y->key ) {
	p_y->left = p_z;
    }
    else {
	p_y->right = p_z;
    }
}


void PreOrder( Node *node )
{
    if ( node != NULL ) {
	printf(" %d", node->key);
	PreOrder( node->left );
	PreOrder( node->right );
    }
}


void InOrder( Node *node )
{
    if ( node != NULL ) {
	InOrder( node->left );
	printf(" %d", node->key);
	InOrder( node->right );
    }
}

Measured memory_bytes: 24468
K = int(input())
A = list(map(int, input().split()))

ans1 = 2
ans2 = 2
for i in range(K - 1, 0, -1):
    if ans1 % A[i] != 0 or ans2 % A[i] != 0 or ans1 < 2 or ans2 < 2:
        print (-1)
        exit()
    ans1 = (ans1 + A[i] - 1) // A[i - 1] * A[i - 1] #最大
    ans2 = (ans2 + A[i - 1] - 1) // A[i - 1] * A[i - 1] #最小
    if ans2 > ans1: #逆転している = 存在できない
        print (-1)
        exit()

    # print (ans1, ans2)

if ans1 % A[0] != 0 or ans2 % A[0] != 0 or ans1 < 2 or ans2 < 2:
    print (-1)
    exit()

print (ans2, ans1 + A[0] - 1)    

Measured memory_bytes: 14432
(function main() {
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  const MAX = 1000;
  const c = Array.from(Array(MAX + 1), () => []);

  let i, j, X, Y, xlen, ylen, maxlen;
  while ((X = lines.shift()) && (Y = lines.shift())) {
    xlen = X.length;
    ylen = Y.length;
    for (i = 0; i <= xlen; i++) c[i][0] = 0;
    for (j = 0; j <= ylen; j++) c[0][j] = 0;

    for (i = 1; i <= xlen; i++) {
      for (j = 1; j <= ylen; j++) {
        if (X[i - 1] === Y[j - 1]) c[i][j] = c[i - 1][j - 1] + 1;
        else c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
      }
    }
    console.log(c[xlen][ylen]);
  }
})();



Measured memory_bytes: 35936
import java.io.*;

class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int h = Integer.parseInt(br.readLine());
		int x=0,y=0;
		for(int i=0 ;i<h ;i++){
			String[] str = br.readLine().split(" ");
			if(str[0].compareTo(str[1])>0){
				x = x + 3;
			}else if(str[0].compareTo(str[1])<0){
				y = y + 3;
			}else{
				x++;
				y++;
			}
		}
		System.out.println(x + " " + y);
	}
}

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7

int N, M, E;
vector<vector<int>> g, rev;
vector<int> topo;
vector<bool> used;

void dfs(int u)
{
	if(used[u])return;
	used[u] = true;
	for(auto& i : g[u])dfs(i);
	topo.push_back(u);
}

void tsort()
{
	REP(i, N)dfs(i);
	reverse(topo.begin(), topo.end());
}

int main()
{
	cin >> N >> M;
	E = N + M - 1;
	g.resize(N);
	rev.resize(N);
	used.resize(N, false);
	REP(i, E)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		rev[b].push_back(a);
	}
	tsort();


	vector<int> pos(N);
	REP(i, N)pos[topo[i]] = i;
	REP(i, N)
	{
		if(i == topo[0])cout << 0 << endl;
		else
		{
			int id = rev[i][0];
			int best = pos[id];
			FOR(j, 1, rev[i].size())
			{
				if(pos[rev[i][j]] > best)
				{
					id = rev[i][j];
					best = pos[rev[i][j]];
				}
			}
			cout << id + 1 << endl;
		}
	}

	cin >> N;


	return 0;
}


Measured memory_bytes: 15868
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound

int main(){
  int H,W,K;
  cin>>H>>W>>K;
  VS S(H);
  rep(i,H) cin>>S[i];
  int ans=1000000;
  rep(i,(1<<(H-1))){
    VI X(H-1);
    int tmp=0;
    rep(j,H-1){
      X[j]=(i>>j)%2;
      if((i>>j)%2) tmp++;
    }
    int num=tmp;
    VI Y(num+1);
    rep(j,W){
      int Z=0;
      VI ko(num+1);
      rep(k,H){
        if(S[k][j]=='1'){
          Y[Z]++;
          ko[Z]++;
        }
        if(k<H-1) if(X[k]==1) Z++;
      }
      int F=0;
      rep(k,num+1){
        if(Y[k]>K){
          if(j==0) tmp=1000000;
          else{
            tmp++;
            F=1;
            break;
          }
        }
      }
      if(F) rep(k,num+1){
        Y[k]=ko[k];
      }
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
}

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

using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    vector<double> a(n);
    double ans = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        ans += 1.0 / a[i];
    }
    ans = 1.0 / ans;
    cout << ans;
    return 0;
}


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





int main(){
  int n;
  cin>>n;
  
  int max=0;
  int maxindex=0;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(abs(a)>=abs(max)){
      max=a;
      maxindex=i;
    }
  }
  maxindex++;
  int m=2*n-1;
  cout<<m<<endl;
  if(max>=0){
    for(int i=1;i<=n;i++){
      cout<<maxindex<<" "<<i<<endl;
    }
    for(int i=1;i<n;i++){
      cout<<i<<" "<<i+1<<endl;
    }
  }else if(max<0){
    for(int i=1;i<=n;i++){
      cout<<maxindex<<" "<<i<<endl;
    }
    for(int i=n;i>1;i--){
      cout<<i<<" "<<i-1<<endl;
    }
  }
  


    return 0;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    const xs = 5.iota.map!(_ => readln.chomp.to!int).array;
    const k = readln.chomp.to!int;
    foreach (i; 0..5) {
        foreach (j; i+1..5) {
            if (xs[j] - xs[i] > k) {
                writeln(":(");
                return;
            }
        }
    }
    writeln("Yay!");
}



Measured memory_bytes: 368
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n = ip()                                     #入力整数1つ
#n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#a.popは10^5あるときTLEしやすい!注意!
#これを消すとなぜかWAになる呪い
pt,px,py = 0,0,0
for i in range(n):
    t,x,y = (int(i) for i in input().split())
    time = t - pt
    dist = abs(x-px)+abs(y-py)
    if dist>time:j(0)
    if (time-dist)%2:j(0)
j(1)


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

const ll maxs = 2e5+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'

void pre(){
    
}

void solve(){
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    ll ans=0;
    if( a >= k ){
        ans += k;
        k -= k;
    }
    else{
        ans += a;
        k -= a;
    }
    k -= b;
    if(k > 0){
        ans -= k;
    }

    cout << ans ;

}

int main(){
    // #ifndef ONLINE_JUDGE
    // freopen("input00.txt","r",stdin);
    // #endif
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}

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

// テーブルを作る前処理

int main(void){
    // Your code here!
    ll A,B;
    cin>>A>>B;
    if(A>9 || B>9){
        cout<<-1<<endl;
    }else{
        cout<<A*B<<endl;
    }
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
typedef pair<long double, long double> pdd;

#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
double dp[70][5500];
#define double long double
void mainmain(){
	int x,y,z;
	while(cin>>x>>y>>z,x||y||z){
		rep(i,70){
			rep(j,5500){
				dp[i][j]=0.0;
			}
		}
		vint r(x);
		double p=1.0/(double)x;
		rep(i,x) cin>>r[i];
		vector<pii> ev(70,mkp(0,0));
		rep(i,z){
			int t1,t2,t3;
			cin>>t1>>t2>>t3;
			if(t2==3) t3*=-1;
			ev[t1]=mkp(t2,t3);
		}
		dp[0][0]=1.0;
		rep(i,y+1){
			if(ev[i].F==5){
				// cout<<"hoge1 "<<i<<endl;
				int next=i+ev[i].S;
				rep(j,5500){
					dp[next][j]+=dp[i][j];
				}
			}
			else{
				rep(j,x){
					int next=i+r[j];
					if(ev[next].F==2||ev[next].F==3){
						rep(k,5400){
							int t=k+ev[next].S;
							dp[next][max(0,t)]+=dp[i][k]*p;
						}
					}
					else if(ev[next].F==1){
						next+=ev[next].S;
						rep(k,5500){
							dp[next][k]+=dp[i][k]*p;
						}
					}
					else{
						rep(k,5500){
							dp[next][k]+=dp[i][k]*p;
						}
					}
				}
			}
		}
		double ans=0.0;
		reep(i,y+1,y+12){
			double tmp=0.0;
			rep(j,5500){
				tmp+=j*dp[i][j];
			}
			ans+=tmp;
		}
		cout<<(int)ans<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

Measured memory_bytes: 4204
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>


using namespace std;

long lcm(long N, long M) {
    if (N < M) return lcm(M, N);
    long product = N * M, buf;
    while (M != 0) {
        buf = N;
        N = M;
        M = buf % M;
    }
    return product / N;
}

int main() {
    long a, b, c, d;
    cin >> a >> b >> c >> d;
    long ccnt = b / c - (a - 1) / c,
         dcnt = b / d - (a - 1) / d,
         cdcnt = b / lcm(c, d) - (a - 1) / lcm(c, d);
    cout << b - a - (ccnt + dcnt - cdcnt) + 1 << '\n';
    return 0;
}


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

const int mN = 100100;
int a[mN];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i=1; i<=m; i++) cin >> a[i], n -= a[i];
	if (n<0) n = -1;
	cout << n;
}

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

int main(){
	int n; cin >> n;
	vector<int> a(n);
	for( auto &k : a ) cin >> k;
	reverse( a.begin(), a.end() );
	map<int, int> m;
	++m[a[0]];
	int cnt = 1;
	for( int i = 1; i < n; ++i ){
		auto itr = m.upper_bound(a[i]);
		if( itr == m.end() ){
			++m[a[i]];
			++cnt;
		} else {
			int prev = itr->first;
			if( m[prev] == 1 ){
				m.erase(itr);
			} else{
				--m[prev];
			}
			++m[a[i]];
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple

ll M = 998244353;


int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	int n,k; cin>>n>>k;
	ll a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	//if(k>=n) cout<<0;
	ll ans=0;
	for(int i=0;i<n-k;i++) ans+=a[i];
	cout<<ans;
	
	
	return 0;
}


Measured memory_bytes: 1792
def start_coord(a)
  a.each_with_index{|hh, h|
    if w = hh.index("S")
      return [h, w]
    end
  }
end

def goal?(coord)
  coord[0] <= 0 || coord[0] >= H-1 || coord[1] <= 0 || coord[1] >= W-1
end

def f(a, k)
  start = start_coord(a)
  return 0 if goal?(start)

  visited = H.times.map{ [false]*W }

  queue = [start]
  visited[start[0]][start[1]] = true
  min = 1.0/0
  dirs = [[1,0], [-1,0], [0,1], [0,-1]]

  while !queue.empty?
    curr = queue.shift
    return 1 if goal?(curr)
    curr.tap{|h, w| min = [min, h, w, H-h-1, W-w-1].min }
    dirs.each{|d|
      h = curr[0] + d[0]
      # next if !h.between?(0, H-1)
      w = curr[1] + d[1]
      # next if !w.between?(0, W-1)
      next if a[h][w] == "#"
      next if (h-start[0]).abs + (w-start[1]).abs > k
      next if visited[h][w]
      queue << [h,w]
      visited[h][w] = true
    }
  end

  1 + min.fdiv(k).ceil
end

H, W, K = gets.split.take(3).map(&:to_i)
A = H.times.map{ gets.chars.take(W) }
p f(A, K)


Measured memory_bytes: 53500
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
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); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int main(){
  string s;
  cin >> s;
  if(s[0] == '7' || s[1] ==  '7' || s[2] == '7')cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

using namespace std;

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

  int ans = 1;
  for (long long i = 2; i * i <= a; i++)
    if (a % i == 0) {
      if (b % i == 0) {
        ans++;
      }
      while (a % i == 0) {
        a /= i;
      }
    }

  ans += (a > 1 && b % a == 0);
  cout << ans << endl;
}


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

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

int main() {
    int k;
    cin >> k;
    string ans = "";
    rep(i,k){
        ans += "ACL";
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
long returnspecidicdigit(long a,long b){
//aの右からb番目を返す
 long a_default = a, b_default = b;
 while(b>0){
  a /= 10;
  if(a<0) {
   cout << "与えられた引数が不正です.a= " << a_default << " :b=" << b_default << endl;
   return 0;
  }
 }
 return a%=10;
}
int main()
{
  int N;
  cin >> N;
  int num = N%10;
  if (num == 7)
  {
    cout << "Yes" << endl;
    return 0;
  }
  num = N/10 % 10;
  if (num == 7)
  {
    cout << "Yes" << endl;
    return 0;
  }
  num = N / 100 % 10;
  if (num == 7)
  {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<string> a;
  for(int i = 0; i < n; i++) {
    string s;
    cin >> s;
    a.push_back(s);
    //cin >> a[i]はだめ.
  }
  sort(a.begin(), a.end());
  int ans = n;
  for(int i = 0; i < n - 1; i++) {
    if(a[i] == a[i + 1]) ans--;
  }
  cout << ans << endl;
}


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

void solve(void){
  

	int n,m;
  cin >> n >> m;
	
  int i;
  long long int A[n],total=0;
  rep(i,n){
    cin >> A[i];
	total+=A[i];
  }
  
  int mmax=0;

  sort(A,A+n);
  
  if(A[n-m]*4*m>=total){
  
    if(n==m){
      
      cout << "Yes" <<endl;
     return; 
    }else if(n!=m&&A[n-m]!=A[n-m-1]){
    cout << "Yes" <<endl;
   return; 
  }}
    
  cout << "No" << endl;
  
  return;
}

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

Measured memory_bytes: 256