akhauriyash/Code-Regression huggingface dataset:
function Main(input) {
	let str = input.toString().split("")
	// 出力に改行があるので削除しておく
	str.pop()
	const num = str.join(".").split("").map( x => ( x == "." ) ? "" : x )
	const l = str.length - 1
	let ans = 0
	for( let i = 0; i < (1<<l); ++i ){
		let tempnum = [...num]
		for( let j = 0; j < l; ++j ){
			if( (i>>j) & 1 ) tempnum[1+2*j] = "+"	
		}
		ans += eval(tempnum.join(""))
	}
	console.log(ans)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"))

Measured memory_bytes: 7884
s = int(input())
p = 10 ** 9 + 7

ans = [0,0,1,1,1]
for i in range(s):
  a = ans[-5]
  b = ans[-4]
  c = ans[-3]
  ans.append( (2 * c + b + a) % p )
print( ans[s-1] )

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

int main(){
 int n, k ;
 vector<int>  v;
 cin >> n >> k;
 for(int i = 1; i<=k; i++){
 int d;
 cin >> d;
  int a[d+1];
 for(int i = 1; i<=d; i++){
     cin >> a[i];
     v.push_back(a[i]);
  }
 }
 int c[n+1] ={0};
  for(int i = 0; i<v.size() ; i++){
   c[v[i]]++;
  }
 int cnt = 0;
 for(int i = 1; i<=n; i++){
   if(c[i])  cnt++;
}
int ans = n - cnt;
 cout <<  ans  <<endl;
return 0;
}

Measured memory_bytes: 3672
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int count = 0;
		String line1st = reader.readLine().toUpperCase();
		String line;
		String[] str;
		while(true) {
			line = reader.readLine();
			if(line.equals("END_OF_TEXT")) {
				break;
			}
			str = line.split(" ", -1);
			for(int i = 0; i < str.length; i++) {
				if(str[i].toUpperCase().equals(line1st)) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 24184
#include<bits/stdc++.h>
using namespace std;
int main()
{
    double n,x=0;
    int i,j;
    scanf("%lf",&n);

    for(i=1;i<=n;i++)
    {
        if(i%2!=0)
            x++;
    }

    printf("%.10f\n",x/n);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

constexpr int MOD = 1000000007;
ll modpow(ll n, ll r, ll mod) {
    if(r == 0) return 1;
    if(n == 0) return 0;
    if(r % 2 == 0) {
        ll tmp = modpow(n, r / 2, mod);
        return tmp * tmp % mod;
    }
    else {
        return n * modpow(n, r - 1, mod) % mod;
    }
}

int main(){
    int A, P;
    read(A, P);
    int piece = 3 * A + P;
    int ans = piece / 2;
    write(ans);
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define fastcin {\
    cin.tie(0);\
    ios::sync_with_stdio(false);\
}
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = a; i >= b; i--)
#define fore(i, a) for(auto &i:a)
#define print(x) cout << x << "\n"
#define SORT(a, n) sort(a, a+n);
#define REVERSE(a,n) reverse(a,a+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VREVERSE(v) reverse(v.begin(), v.end());
#define MOD 1000000007
#define yes "YES"
#define no "NO"
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

bool pmod(string s, int m, int p) {
    int size = s.size(), tmp = 0;
    rep(i, 0, size) {
        tmp = (tmp*p + s[i]-'0') % m;
    }
    bool b;
    if(tmp) b = false;
    else b = true;
    return b;
}

bool dp[1][1] = {};
void solve_dp(int n, int k, vi a) {
    rep(i, 0, n) {
        rep(j, 0, k+1) {
            if(dp[i][j]) {
                dp[i+1][j] = true;
                if((j+a[i])<=k) {
                    dp[i+1][j+a[i]] = true;
                }
            }
        }
    }
}

int main() {
    fastcin;
    ll a, b, c, k, ans;
    cin >> a >> b >> c >> k;
    if(k%2==0) ans = a - b;
    else ans = b - a;
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int a=0,j,i,n,k,d,have_s;
  int people,flag[100]={0};
  
  scanf("%d %d",&n,&k);//人数と菓子の種類
  for(i=1; i<=k; i++){
    scanf("%d",&have_s);//お菓子を持つ人数
    for(j=1; j<=have_s; j++){
      scanf("%d",&people);//どの人がもっているのか
      flag[people]++;//どの人がもってるか個数を入れた
    }
  }

  for(i=1; i<=n; i++){
    if(flag[i]==0)
      a++;
  }
  printf("%d\n",a);
  return 0;
}

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

using namespace std;

int main()
{
    #ifdef HOME
        freopen("input.txt", "rt", stdin);
    #endif // HOME
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        ans += r - l + 1;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
using namespace std;
int x[100005],y[100005],t[100005];
int main()
{
	int n,f=1;scanf("%d",&n);
	for(int i=1;i<=n&&f;i++)
	{
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
		int s=t[i]-t[i-1]-abs(x[i]-x[i-1])-abs(y[i]-y[i-1]);
		if(s<0||s&1) f=0;
	}
	if(f) printf("Yes");else printf("No");
	return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#define r register
int n;
char ch[305][305];
#define loop(x) (x>=n?(x-n):x)
int main(){
	scanf("%d",&n);r int ans=0;
	for(r int i=0;i<n;i++)scanf("%s",ch[i]);
	for(r int i=0,f=1;i<n;i++,f=1){
		for(r int j=0;j<n&&f;j++)
			for(r int k=j+1;k<n&&f;k++)
				f=(ch[j][loop(k+i)]==ch[k][loop(j+i)]);
		ans+=n*f;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;
void solve(){
    int n,k;cin>>n>>k;
    int cnt=1;
    fol(i,n){
        if (cnt*2>cnt+k){
            cnt+=k;
        }else{
            cnt *=2;
        }
    }
    cout << cnt << endl;
}

int main(){
//option:-std=c++0x
    solve();
    return 0;
}


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

int main() {
	long long T1, T2;
	cin >> T1 >> T2;
	long long A1, A2, B1, B2;
	cin >> A1 >> A2 >> B1 >> B2;
	long long X = (A1 - B1)*T1;
	long long Y = (A2 - B2)*T2;
	if (X > 0) {
		X = -1 * X;
		Y = -1 * Y;
	}
	if (0 == (X + Y)) {
		cout << "infinity" << endl;
		return 0;
	}
	if (0 > (X + Y)) {
		cout << 0 << endl;
		return 0;
	}
	long long ans = 0;
	ans = (-1 * X) / (X + Y);
	ans *= 2;
	if (0 == (-1*X)%(X+Y)) {
		ans--;
	}
	ans++;
	cout << ans << endl;
	return 0;
}



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

int main() {
	string S;
	cin >> S;
	int len = S.size();
	bool flag = false;
	for (int i = 0; i < len - 1; i++) {
		if (S.substr(i, 2) == "AC") {
			flag = true;
		}
	}
	if (flag) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
//#define kk
#define int long long
#define FOR(i, n) for(int i=1; i<=n; i++)
#define ff first
#define ss second
#define ll int
#define inf 1000000000
#define pb push_back
#define mod 1000000007
 
const long long INF=1e18+5;
typedef pair<int, int> pi;

int arr[405];
int dp[405][405];

int get(int i, int j){
	if(i>=j) return 0;
	if(dp[i][j]!=-1) return dp[i][j];
	
	int sum=0;
	for(int k=i; k<=j; k++){
		sum+=arr[k];
	}
	
	int ans=INF;
	for(int k=i; k<=j-1; k++){
		int temp=get(i, k)+get(k+1, j)+sum;
		ans=min(temp, ans);
	}
	return dp[i][j]=ans;
}

void solve(){
	int n;
	cin>>n;
	
	FOR(i, n) cin>>arr[i];
	
	memset(dp, -1, sizeof dp);
	
	cout<<get(1, n)<<endl;
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cout<<fixed<<setprecision(10);
	
	#ifdef kk
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	
	int T=1;
	//cin>>T;
	
	while(T--){
		solve();
	}
}


Measured memory_bytes: 4908
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll INF = 1LL << 62;
const int inf = 1 << 30;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    cout << 800 * n - 200 * (n / 15) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string a,b,c;
    cin >>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

int main()
{
    std::vector<long> v;
    int n;
    int k;
    std::cin >> n;
    std::cin >> k;
    for (int i = 0; i < n; i++)
    {
        long temp;
        std::cin >> temp;
        v.push_back(temp);
    }
    std::sort(v.begin(), v.end());

    long min = (std::numeric_limits<long>::max)();
    for (std::vector<long>::iterator it = v.begin();
         it < v.end() - k + 1;
         it++)
    {
        long sub = std::abs(*it - *(it + k - 1));
        if (sub < min)
            min = sub;
        if (min == 0)
        {
            std::cout << 0;
            return 0;
        }
    }
    std::cout << min;
    return 0;
}

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

int main() {
  vector<long long> prime(1000000, 0);
  prime.at(0) = 1; prime.at(1) = 1;
  for(int i = 0; i < 1000000; i++){
    if(prime.at(i) == 0){
      long long j = i * 2;
      while(j < 1000000){
        prime.at(j) = 1;
        j += i;
      }
    }
  }
  long long x; cin >> x;
  for(int i = x; i < 1000000; i++){
    if(prime.at(i) == 0){
      cout << i;
      return 0;
    }
  }
}


Measured memory_bytes: 8064
import collections

n = int(input())

li=[]


for i in range(n):
    li.append(input())

cnt = collections.Counter(li)
S = cnt.most_common()


C =len(cnt)

li_1 = [S[0][0]]

for i in range(C-1):
    if S[i][1] == S[i+1][1]:
        li_1.append(S[i+1][0])
    else:
        break

li_1.sort()

for i in li_1:
    print(i)


Measured memory_bytes: 50284
#include <bits/stdc++.h>
#define rep( i, n ) for (int i = 0; i < ( long long )(n); i++)
using namespace std;
int main(){
	long long n;
	long long ans = 0;
	
	cin >> n;
	
	vector< pair < long long , long long > > ts( n );

	rep( i, n ){
		long long x , l;
		cin>>x>>l;
		ts.at( i ).first = x + l;
		ts.at( i ).second = x - l;
	}
	
	sort( ts.begin( ) , ts.end( ) );
	
	long long cur = -1e9;
	rep( i, n ){
		if( cur <= ts.at( i ).second ){
			ans++;
			cur = ts.at( i ).first;
		}
	}	
	cout<<ans;
}


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

int main(){
  int N, W;
  cin >> N >> W;
  ll w[N], v[N];
  rep(i, N) cin >> w[i] >> v[i];
  ll dp[N+1][W+1];
  rep(i, N+1){
    rep(j, W+1) dp[i][j] = 0;
  }
  rep(i, N){
    rep(j, W+1){
      if(j - w[i] >= 0) dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i]);
      else dp[i+1][j] = dp[i][j];
    }
  }
  cout << dp[N][W] << endl;
  return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, Y;
  cin >> N >> Y;
  for (int i = 0; i <= N; i++) {
    if (i * 10000 > Y) break;
    for (int j = 0; j <= N; j++) {
      if (i * 10000 + j * 5000 > Y) break;
      if (i * 10000 + j * 5000 + (N - i - j) * 1000 == Y && N - i - j >= 0) {
        cout << i << " " << j << " " << N - i - j << '\n';
        return 0;
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair<int,int>
#define f first
#define se second
using namespace std;
double pi=acos(-1.0);
int m=1000000007;
bool cmp2(int n,pii p)
 {return n<p.f;}
int abst(int a)
{return a<0?-a:a;}
struct HASH{
  size_t operator()(const pii &x)const{
    return (size_t) x.first * 37U + (size_t) x.second;}};
int Pow(int n,int x){int ans=1;
 while(x>0)
 {if(x&1)ans=(ans*n)%m;n=(n*n)%m;x=x>>1;}
 return ans;}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int32_t main(){
//ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int dp[n];
dp[0]=0;
for(int i=1;i<n;i++)
dp[i]=INT_MAX;
for(int i=1;i<n;i++)
for(int j=i-1;j>=0 && j>=i-k;j--)
dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
cout<<dp[n-1];
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int main(){cout<<fixed<<setprecision(20);
		   int a;
           map<int,int> cnt;
           rep(i,0,4){
            cin>>a;
             cnt[a]++;
           }
           YES(cnt[1]&&cnt[9]&&cnt[7]&&cnt[4]);
}

Measured memory_bytes: 3608
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct{
	long long int code;
	int steps;
} puzz;

int SW,q[10000000][14],size[2][30000];
long long int FR,TO;
puzz* hash[2][30000][100];

void swap (int* x,int* y){
	int z;
	z=*x;
	*x=*y;
	*y=z;
}

long long int convert(int a[]){
	long long int ret=0;
	int i;
	for(i=0;i<13;i++)ret=ret*13+a[i];
	return ret;
}

void hashadd(long long int code,int step,int loc){
	int ccc=code%30000;
	puzz* ppp=(puzz*)malloc(sizeof(puzz));
	ppp->code=code;
	ppp->steps=step;
	if(size[loc][ccc]>99){fprintf(stderr,"SIZE OVER!! (%d)\n",ccc);return;}
	hash[loc][ccc][size[loc][ccc]]=ppp;
	size[loc][ccc]++;
}

int hashsearch(long long int code,int loc){
	int ccc=code%30000;
	int i=size[loc][ccc]-1;
	for(;i>=0;i--){
		if(hash[loc][ccc][i]->code==code)return hash[loc][ccc][i]->steps;
	}
	return -1;
}

void mark(int x,int y){
	int k;
	long long int cd;

	swap(&q[FR][x],&q[FR][y]);
	cd=convert(q[FR]);

	if(hashsearch(cd,SW)<0){
		for(k=0;k<14;k++){q[TO][k]=q[FR][k];}
		q[TO][13]++;
		if(SW==0)hashadd(cd,q[TO][13],SW);
		TO++;
	}

	swap(&q[FR][x],&q[FR][y]);

}

void check(){
	if(q[FR][0]==0){mark(0,2);}
	if(q[FR][1]==0){mark(1,2);mark(1,5);}
	if(q[FR][2]==0){mark(2,0);mark(2,1);mark(2,3);mark(2,6);}
	if(q[FR][3]==0){mark(3,2);mark(3,7);}
	if(q[FR][4]==0){mark(4,5);}
	if(q[FR][5]==0){mark(5,1);mark(5,4);mark(5,6);mark(5,9);}
	if(q[FR][6]==0){mark(6,2);mark(6,5);mark(6,7);mark(6,10);}
	if(q[FR][7]==0){mark(7,3);mark(7,6);mark(7,8);mark(7,11);}
	if(q[FR][8]==0){mark(8,7);}
	if(q[FR][9]==0){mark(9,5);mark(9,10);}
	if(q[FR][10]==0){mark(10,6);mark(10,9);mark(10,11);mark(10,12);}
	if(q[FR][11]==0){mark(11,7);mark(11,10);}
	if(q[FR][12]==0){mark(12,10);}
}


int main(){
	int i,ans;
	long long int cd;

	for(i=1;i<12;i++)q[0][i]=i;
	q[0][0]=0;q[0][12]=0;q[0][13]=0;
	hashadd(convert(q[0]),0,0);

	FR=0;TO=1;SW=0;

	while(FR<TO && q[FR][13]<=13){
		check();
		FR++;
	}

	while(scanf("%d",&q[0][0])*q[0][0]>=0){
		for(i=1;i<13;i++)scanf("%d",&q[0][i]);
		q[0][13]=0;FR=0;TO=1;SW=1;ans=9999;
		for(i=0;i<30000;i++)size[1][i]=0;

		while(FR<TO){
			cd=hashsearch(convert(q[FR]),0);
			if(cd>=0){
				ans=(int)cd+q[FR][13];
				break;
			}
			if(q[FR][13]<6)check();
			FR++;
		}

		if(ans>20)printf("NA\n"); else printf("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 36792
($H,$_)=glob<>;
push@t,[glob<>]for(0..9);
for$k(0..9){for$i(0..9){for$j(0..9){
    $t[$i][$j]=$t[$i][$k]+$t[$k][$j] if $t[$i][$j]>$t[$i][$k]+$t[$k][$j]
}}}
$c[$_]=$t[$_][1]for(0..9);
$t=$c[10]=0;
map{$t+=$c[$_]}glob<> for(1..$H);
print$t

Measured memory_bytes: 896
def li():
    return list(map(int, input().split()))
def mi():
    return map(int, input().split())
def ii():
    return int(input())
def lim(N):
    return [int(input()) for i in range(N)]

N = ii()
a = lim(N)

current = 1
result = 1

for i in range(N):
    if a[current - 1] == 2:
        print(result)
        break
    else:
        current = a[current - 1]
        result += 1
else:
    print(-1)

Measured memory_bytes: 7084
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B
import Data.List
import Data.Char (isSpace)
import Data.Vector.Unboxed.Mutable (IOVector, STVector)
import qualified Data.Vector.Unboxed.Mutable as VM
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS

main :: IO ()
main = do
  [n, m] <- f
  solve n <$> (IS.fromList <$> replicateM m g) >>= print
  where
    f = readil B.readInt <$> B.getLine
    g = readi B.readInt <$> B.getLine

solve :: Int -> IntSet -> Int
solve n st = runST $ do
  sv <- VM.replicate (n + 1) 0 :: ST s (STVector s Int)
  VM.write sv 0 1
  if IS.member 1 st
    then VM.write sv 1 0
    else VM.write sv 1 1
  forM_ [2 .. n] $ \i -> do
    if IS.member i st
      then VM.write sv i 0
      else do
        x2 <- VM.read sv (i - 2)
        x1 <- VM.read sv (i - 1)
        VM.write sv i ((x1 + x2) `mod` md)
  VM.read sv n
  where
    md = 1000000007

readi :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> a
readi f s = let Just (n, _) = f s in n

readil :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> [a]
readil f = unfoldr $ \s -> do
  (n, s') <- f s
  return (n, B.dropWhile isSpace s')


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

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

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

struct edge {
	int to, cost;
	edge(int t,int c):to(t),cost(c) {}
};


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

int k;
ll dp[100001];

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

	cin>>k;
	REP(i,k+1) dp[i]=LINF;
	deque<P> dq;
	dq.pb(P(1,1));
	while (!dq.empty()) {
		P p=dq.front();dq.pop_front();
		if(dp[p.fi]<p.se) continue;
		dp[p.fi]=p.se;
		if(dp[p.fi*10%k]>p.se) dq.pf(P(p.fi*10%k,p.se));
		if(p.fi%10!=9&&dp[(p.fi+1)%k]>p.se+1) dq.pb(P((p.fi+1)%k,p.se+1));
	}
	cout<<dp[0]<<endl;

	return 0;
}


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

void draw(char g[20][20], int ci, int cj){
    g[ci][cj] = '0';
    int di[] = {0,0,1,-1};
    int dj[] = {1,-1,0,0};
    rep(d,4){
        int ni = ci + di[d];
        int nj = cj + dj[d];
        if(ni >= 12 || nj >= 12 || ni < 0 || nj < 0 || g[ni][nj] == '0') continue;
        draw(g,ni,nj);
    }
}

int solve(char g[20][20]){
    int ans = 0;
    rep(i,12)rep(j,12){
        if(g[i][j] == '1'){
            ++ans;
            draw(g,i,j);
        }
    }
    return ans;
}

int main(){
    char g[20][20];
    while(~scanf("%s",g[0])){
        rep(i,11) scanf("%s",g[i+1]);
        printf("%d\n",solve(g));
    }
}

Measured memory_bytes: 1136
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define MAX_N 200000

int NC[MAX_N]; 

int N,K;


class CompareDist
{
public:
    bool operator()(pair<int,int> n1,pair<int,int> n2) {
        return n1.first<n2.first;
    }
};


int main(){

    cin >> N >> K ;
    priority_queue<int, vector<int> , greater<int> > q;
    for(auto i = 0; i<N; ++i){
        NC[i] = 0;
    }
    for(auto i = 0; i<N; ++i){
        int ai;
        cin >> ai;
        NC[ai-1]++;
    }
    for(auto i = 0; i<N; ++i){
        if(NC[i] != 0) q.push( NC[i] );
    }
    int delta = q.size() - K;
    if(delta <= 0){ cout << 0 << endl; return 0;}
    int ans = 0;
    while(!q.empty() && delta != 0 ){
        auto a = q.top();
        q.pop();
        ans = ans+a;
        delta--;
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

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

  int k,x;
  while(cin >> k >> x){
    vector<int> ans;
    FORE(i,x-k+1,x+k-1){
      if(i>=-1000000 and i<=1000000) ans.push_back(i);
    }
    join(cout, ALL(ans));
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string S, T;
	cin >> S >> T;

	if (S.size() < T.size()) {
		puts("UNRESTORABLE");
		return 0;
	}
	//こっち
	/*if (S.size() == T.size() && count(all(S), '?') != S.size()) {
		puts("UNRESTORABLE");
		return 0;
	}*/

	reverse(all(S));
	reverse(all(T));
	int k = T.size();
	bool elf = false;

	//?について調べる
	for (int i = 0; i < S.size() - k - 1; ++i) {
		bool res = true;
		string s = S.substr(i, k);
		for (int j = 0; j < k; ++j) {
			if (s[j] == '?') continue;
			if (s[j] != T[j]) res = false;
		}
		if (res) {
			for (int j = 0; j < k; ++j) {
				S[i + j] = T[j];
			}
			elf = true;
			break;
		}
	}

	if (!elf) {
		puts("UNRESTORABLE");
		return 0;
	}

	rep(i, S.size()) {
		if (S[i] == '?') S[i] = 'a';
	}

	reverse(all(S));

	dunk(S);

	return 0;
}

Measured memory_bytes: 256
import sys

S = input()

S = S[::-1]

chars = ['dreamer', 'eraser', 'dream', 'erase']
chars = [char[::-1] for char in chars]

while 1:
    end_flag = 1
    for char in chars:
        if ( S.find(char) == 0):
            S = S[len(char):]
            end_flag = 0

            if S == '':
                print('YES')
                sys.exit()
    if end_flag ==1:
            print('NO')
            sys.exit()

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main()
{
      int n,k;
       cin>>n>>k;

      int r,s,p;
       cin>>r>>s>>p;

        string t;
         cin>>t;

         long long int total=0;
         bool value[n];

       for(int i=0;i<t.length();i++)
       {
          if(i < k)
          {
             if(t[i]=='p')
               total+=s;

             else if(t[i]=='r')
              total+=p;

              else
              total+=r;

              value[i]=true;
          }
          else
          {
             if(t[i]==t[i-k])
             {
                 if(value[i-k]==false)
                    value[i]=true;

                  else
                  value[i]=false;
             }
             else
                value[i]=true;
          }
       }
         for(int i=k;i<t.length();i++)
         {
               if(t[i]=='s' && value[i]==true)
                total+=r;

              else if(t[i]=='r' && value[i]==true)
               total+=p;

               else if(t[i]=='p' && value[i]==true)
                total+=s;
         }
          cout<<total;
}


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

int main()
{
    int n,k;
    cin >> n >> k;
    int ans;
    ans = log10(n)/log10(k) + 1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<int> v[100001];
bool visited[100001];
void dfs(int u){
	if(visited[u]) return;
	visited[u]=true;
	for(int i=0;i<v[u].size();i++){
		dfs(v[u][i]);
	}
}
int main(){
	memset(visited,false,sizeof(visited));
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!visited[i]){
			dfs(i);
			++ans;
		}
	}	
	cout<<ans;
}

Measured memory_bytes: 8960
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
 
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpi;
typedef vector<pair<ll, ll> > vpl;



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
  cin >> n;
  ll taka=1, aoki=1;
  rep(i,n){
    int t, a;
    cin >> t >> a;
    ll k = max((taka+t-1)/t, (aoki+a-1)/a);
    taka = k*t;
    aoki = k*a;
  }
  cout << taka+aoki << endl;
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, K = LI()
A = [False] * N
for _ in range(K):
    ss = I()
    D = LI()

    for d in D:
        A[d-1] = True

ans = 0
for a in A:
    if not a:
        ans += 1

print(ans)


Measured memory_bytes: 82692
#include<iostream>
#include<algorithm>
using namespace std;
#define INFTY 1000000001
int cnt;
long long int totalcnt;

void merge(int *A, int left, int mid, int right) {
    int na = mid - left;
    int nb = right - mid;
    int L[na+1], R[nb+1];
    for (int i=0; i<na; i++) {
        L[i] = A[left+i];
    }
    for (int i=0; i<nb; i++) {
        R[i] = A[mid+i];
    }
    L[na] = INFTY;
    R[nb] = INFTY;
    int i=0, j=0;
    long long int res = 0;
    for (int k = left; k<right; k++) {
        cnt ++;
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i = i+1;
        } else {
            A[k] = R[j];
            j = j + 1;
            res += na-i;
        }
    }
    totalcnt += res;
}

void mergeSort(int *A, int left, int right) {
    if (left + 1 < right) {
        int mid = (left+right)/2;
        mergeSort(A,left, mid);
        mergeSort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;
    int S[n];
    for (int i=0; i<n; i++) {
        cin >> S[i];
    }
    cnt = 0;
    totalcnt = 0;
    mergeSort(S, 0, n);
    cout << totalcnt << endl;
    return 0;
}



Measured memory_bytes: 4676
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,a[205],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2;++i)scanf("%d",a+i);
    sort(a+1,a+n*2+1);
    for(int i=1;i<=n*2;i+=2)ans+=a[i];
    printf("%d\n",ans);
    //system("pause");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int n,m,q;
ll ans = 0;
vector<int> a(101),b(101),c(101),d(101);

void dfs(vector<int> v, int las) {
  if (v.size() == n) {
    ll sum = 0;
    REP(i,q) {
      if (v[b[i]] - v[a[i]] == c[i]) sum += d[i];
    }
    ans = max(ans,sum);
    return;
  }

  for (int i = las; i <= m; i++) {
    vector<int> nv = v;
    nv.push_back(i);
    dfs(nv, i);
  }
}

int main() {
  cin >> n >> m >> q;
  REP(i,q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--; b[i]--;
  }
  vector<int> v;
  dfs(v, 1);
  COUT(ans);
  return 0;
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def solve(X: int):
    L = eratosthenes_sieve(200000)
    mn = 0
    for l in L:
        if l >= X:
            mn = l
            break
    print(mn)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5304
//
//  main.cpp
//  BBQ_Easy
//
//  Created by Uttam Datta on 30/05/19.
//  Copyright © 2019 Uttam Datta. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int ans(vector <int> N){
    sort(N.begin(), N.end());
    int ans = 0;
    for(size_t i = 0; i < N.size(); i += 2){
        ans += min(N[i], N[i+1]);
    }
    return ans;
}

int main(){
    int N;
    cin >> N;
    vector <int> L(2*N);
    for(int i =0; i < 2*N; i++){
        cin >> L[i];
    }
    int res = ans(L);
    cout << res << endl;
    return 0;
}


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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  string s;
  cin >> s;
  if (s.back() == '3') {
    cout << "bon";
  } else if (string("0168").find(s.back()) != string::npos) {
    cout << "pon";
  } else {
    cout << "hon";
  }
  return 0;
}

Measured memory_bytes: 3648
using System;

namespace ABC079_D___Wall
{
    class Program
    {
        static void Main(string[] args)
        {
            var HW = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var changeCosts = new int[10, 10];
            for (int i = 0; i < 10; i++)
            {
                var read = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                for (int j = 0; j < 10; j++) changeCosts[i, j] = read[j];
            }

            for (int via = 0; via < 10; via++)
                for (int from = 0; from < 10; from++)
                    for (int to = 0; to < 10; to++)
                        changeCosts[from, to] = Math.Min(changeCosts[from, to], changeCosts[from, via] + changeCosts[via, to]);

            var sumCost = 0;
            for (int i = 0; i < HW[0]; i++)
            {
                var read = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                foreach (int r in read) if (r != -1) sumCost += changeCosts[r, 1];
            }
            Console.WriteLine(sumCost);
        }
    }
}


Measured memory_bytes: 15316
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    bool used[1000010] = {};
    int s; cin >> s;
    int cnt = 1;
    while(true) {
        if (!used[s]) {
            used[s] = true;
            if (s % 2 == 0) s /= 2;
            else s = s * 3 + 1;
        } else {
            cout << cnt << endl;
            return 0;
        }
        cnt++;
    }

    return 0;
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int cd(int a, int b, int n){
  int i, j=0;
  int tmp[100];
  for(i=a; i>0; i--){
    if(a%i == 0 && b%i == 0){
      tmp[j] = i;
      j++;
    }
  }
  return tmp[n-1];
}

int main(){
  int A, B, K, tmp;
  cin >> A >> B >> K;
  if(A < B){
    tmp = A; A = B; B = tmp;
  }
  cout << cd(A, B, K) << endl;
  return 0;
}


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

#define dd ch=getchar()
inline int read()
{
	int x=0;char dd;bool f=false;
	while(!isdigit(ch))f|=ch=='-',dd;
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
	return f?-x:x;
}
#undef dd
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+48);
}
#define writeln(x) (write(x),putchar('\n'))
#define writesp(x) (write(x),putchar(' '))

const int N=17,M=N*N;

int n,m;
int f[1<<15][N],sum[1<<15];//sum表示联通块状态为i的时候的边权和 
//int minn[1<<15][N];//minn[i][j]表示联通块状态为i的时候跟j连接的最小花费 
struct node
{
	int v,w,nxt;
}a[M<<1];
int head[N],cnt=0;
inline void add(int u,int v,int w)
{
	a[++cnt].v=v;
	a[cnt].w=w;
	a[cnt].nxt=head[u];
	head[u]=cnt;
}
bool vis[N][N];

int main()
{
	n=read(),m=read();
	int edge_sum=0;
	for(int i=1,u,v,w;i<=m;i++)
	{
		u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
		edge_sum+=w;
	}
	int tot=(1<<n)-1;
	for(int s=0;s<=tot;s++)
	{
		memset(vis,false,sizeof(vis));
		for(int u=1;u<=n;u++)
			if(s&(1<<(u-1)))
				for(int i=head[u];i;i=a[i].nxt)
				{
					int v=a[i].v,w=a[i].w;
					if(s&(1<<(v-1))&&!vis[u][v])sum[s]+=w,vis[u][v]=vis[v][u]=1;
				}
	}
//	memset(minn,0x3f,sizeof(minn));
//	for(int s=0;s<=tot;s++)
//		for(int u=1;u<=n;u++)
//			if(!(s&(1<<(u-1))))
//				for(int i=head[u];i;i=a[i].nxt)
//				{
//					int v=a[i].v,w=a[i].w;
//					if(s&(1<<(v-1)))minn[s][u]=min(minn[s][u],w);
//				}
	memset(f,-0x3f,sizeof(f));f[1][1]=0;
	for(int s=1;s<=tot;s++)
		for(int u=1;u<=n;u++)
			if(s&(1<<(u-1)))
			{
				for(int i=(s-1)&s;i;i=(i-1)&s)
					if(i&(1<<(u-1)))
						f[s][u]=max(f[s][u],f[i][u]+sum[(s^i)|(1<<(u-1))]);
				for(int i=head[u];i;i=a[i].nxt)
				{
					int v=a[i].v,w=a[i].w;
					if(s&(1<<(v-1)))continue;
					int sv=s|(1<<(v-1));
					f[sv][v]=max(f[sv][v],f[s][u]+w);
				}
			}
	write(edge_sum-f[tot][n]);
	return 0;
}
/*

设f[i][j]表示现在选择的状态为i，结尾为j的最大答案 
最终答案肯定是一条链上挂着子图，且是连通图 
因为是一直连边到终点，所以中间不能有跟已经选择的点连边的操作  
那么直接dp 
两种选择  
①在原链上增加一个点 
②撸一个联通块出来挂在当前点下面 

*/

Measured memory_bytes: 2688
#include<iostream>
#include<string>
using namespace std;
 
int main()
{
  string s;
  cin >> s;
  
  int count = 0;
  auto tail = s.end() - 1;
  auto head = s.begin();
  while(head < tail) {
    if(*head != *tail) count++;
    head++;
    tail--;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		
		int []aa = new int [a];
		int []bb = new int [b];
		
		int mina = 100000000;
		int minb = 100000000;
		
		for(int i = 0 ;i < a ;i++) {
			aa[i] = Integer.parseInt(sc.next());
			mina = Math.min(mina, aa[i]);
		}
		for(int i = 0 ;i < b ;i++) {
			bb[i] = Integer.parseInt(sc.next());
			minb = Math.min(minb, bb[i]);
		}
		
		int ans  = mina + minb;
				
		
		for(int i = 0 ;i < m ;i++) {
			int x = Integer.parseInt(sc.next());
			int y = Integer.parseInt(sc.next());
			int z = Integer.parseInt(sc.next());
			int temp = aa[x-1] +bb[y-1] - z;
			ans = Math.min(temp, ans);
		}
		
		System.out.println(ans);
		
	}

}


Measured memory_bytes: 91124
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

long long n;

int main(){
	scanf("%lld" , &n);
	long long ans = (long long)2 * (n / (long long)11);
	if(n % 11 > 0) ++ans;
	if(n % 11 > 6) ++ans;
	printf("%lld\n" , ans);
	return 0;
}


Measured memory_bytes: 128
H, W, K = map(int, input().split())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
s = sum([sum(x) for x in X])
k = 0
ANS = [[-1] * W for _ in range(H)]
for i in range(H):
    t = sum(X[i])
    if t == 0 and k == 0:
        continue
    if t == 0:
        for j in range(W):
            ANS[i][j] = ANS[i-1][j]
        continue
    
    c = 0
    for j in range(W):
        if X[i][j]: c += 1
        ANS[i][j] = k + max(c, 1)
    k += t
for i in range(H)[::-1]:
    for j in range(W):
        if ANS[i][j] < 0:
            ANS[i][j] = ANS[i+1][j]
for ans in ANS:
    print(*ans)

Measured memory_bytes: 48732
package main

import "fmt"

func main(){
  var N int
  fmt.Scan(&N)

  C := make([]int , N-1)
  S := make([]int , N-1)
  F := make([]int , N-1)
  for i :=0; i< N-1; i++{
    fmt.Scan(&C[i], &S[i], &F[i])
  }
  // fmt.Println(C,S,F)
  for i := 0; i< N; i++{ //i番目の駅について
    t := 0
    // print("i",i)
    if i == N-1{
      fmt.Println(0)
      break
    }
    for j:= i; j<N-1 ;j++{
      // print("j",j)
      if t>= S[j]{
        waitingTime := 0
        if t%F[j] == 0{
          waitingTime = 0
        }else{
          waitingTime = F[j] - t%F[j]
        }
        t += waitingTime //待ち時間
        t += C[j] //電車に乗る時間
      }else{
        t = S[j]
        t += C[j]
      }
    }
    fmt.Println(t)
  }
}


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

int main() {
	int n;
	while (cin >> n, n) {
		vector<P>v;
		rep(i, n) {
			int a, b; cin >> a >> b;
			v.push_back(P(b, a));
		}
		sort(v.begin(), v.end());
		int sum = 0;
		rep(i, n) {
			sum += v[i].second;
			if (sum > v[i].first) {
				puts("No");
				goto p;
			}
		}
		puts("Yes");
	p:;
	}
}

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

int main() {
  int N; cin >> N;
  set<int> S;
  for (int i = 0; i < N; i++) {
    int a; cin >> a;
    S.insert(a);
  }
  if (S.size() == N) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 9600
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();

        int innerRating;

        if (n >= 10) {
            innerRating = r;
        } else {
            innerRating = r + 100 * (10 - n);
        }

        System.out.println(innerRating);
    }
}


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

int main() {
    int N;
    cin >> N;
    vi a(N), b(N), c(N);
    rep(i, N){
        cin >> a[i];
    }
    ll X = 0LL;
    rep(i, N) {
        cin >> b[i];
        c[i] =a[i] - b[i];
        X += c[i];
    }
    if(X>0) {
        cout << "No" << endl;
        return 0;
    }
    X = -X;
    ll A=0LL, B=0LL;
    rep(i, N) {
        if(c[i]>0) {
            B += c[i];
        } else {
            if(c[i]%2) {
                A += (1-c[i])/2;
                ++B;
            } else {
                A += (-c[i])/2;
            }
        }
    }
    if((X-A)*2 == (X-B) && X>=A) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
int main()
{
	LL A,B,ans;
	scanf("%lld%lld",&A,&B);
	if(A==B){
		printf("1"); return 0;
	}
	int r=60,k;
	while( ( A&( 1ll<<r ) ) == ( B&( 1ll<<r ) ) ) r--;
	A &= ( 1ll<<(r+1) )-1; B &= ( 1ll<<(r+1) )-1;
	k=r-1;
	while( ( B&(1ll<<k) )==0 && (k>=0) ) k--;
	ans=(1ll<< r+1)-A;
	if( A>( 1ll<< k+1 ) ) ans-=A-(1ll<< k+1);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
 
class Program{
    static void Main(){
        string s = Console.ReadLine();
        string ans = "No";
        if(((s.Contains('N') && s.Contains('S')) || (!s.Contains('N') && !s.Contains('S'))) 
        && ((s.Contains('W') && s.Contains('E')) || (!s.Contains('W') && !s.Contains('E')))){
            ans = "Yes";
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 2776
#include <iostream>
using namespace std;
bool isp(int n) {
	if (n <= 1) return false;
  	if (n <= 3) return true;
  	for (int i = 2; i * i <= n; i++) if (n % i == 0) return 0;
  	return 1;
}
int main() {
	int n; cin >> n;
  	while (!isp(n)) ++n;
  	cout << n << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
using namespace std;

int main()
{
    int count=0;
    cin >> count;
    
    int value=0, min=INT_MAX, max=INT_MIN;
    long long sum=0;
    for (int i=0; i<count; ++i)
    {
        cin >> value;
        if (value < min)    min = value;
        if (value > max)    max = value;
        sum += value;
    }
    cout << min << " " << max << " " << sum << endl;
    
    return 0;
}

Measured memory_bytes: 1168