akhauriyash/Code-Regression huggingface dataset:
gets
v = gets.chomp.split.map(&:to_i)

vv = v.sort
diff = 0
v.size.times do |i|
  next if v[i] == vv[i]
  diff += 1
  break if diff > 2
end

puts(diff % 2 == 0 ? 'YES' : 'NO')


Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
	int A, B;
	cin >> A >> B;
	if (A == 1) {
		if (B == 1) {
			printf("Draw\n");
			return 0;
		} else {
			printf("Alice\n");
			return 0;
		}
	}
	if (B == 1) {
		printf("Bob\n");
		return 0;
	}
	if (A > B) {
		printf("Alice\n");
		return 0;
	} else if (A < B) {
		printf("Bob\n");
		return  0;
	} else {
		printf("Draw\n");
		return 0;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int mod=1e9+7;
int f[maxn],s[maxn];
int judge[maxn];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int i,l,j;
    ll ans=1;
    for(i=1;i<=n;i++){
        cin>>f[i];
        judge[f[i]]++;
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            if(judge[f[i]]==2&&!s[f[i]]){
                ans*=2;
                ans%=mod;
                s[f[i]]=1;
            }
            if(judge[f[i]]!=2){
                ans=0;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vl a(n);
    cin >> a;
    ll ans = 0;
    while(true) {
        int ind = -1;
        rep(i,n) if(a[i] > n-1) {
            if(ind == -1 or a[ind] < a[i]) ind = i;
        }
        if(ind == -1) break;
        ll l = a[ind]/n;
        ans += l;
        a[ind] %= n;
        rep(i,n) if(i != ind) a[i] += l;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3560
n=int(input())
x=list(map(int,input().split()))
p=0
for i in range(n):
    p+=2*x[i]
  
p1=p//(2*n)
p2=p1+1

    
ans1=0
ans2=0
for j in range(n):
    ans1+=(x[j]-p1)**2
    ans2+=(x[j]-p2)**2
    
print(min(ans1,ans2))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mxn= 5e4+5;
// check for forloop
// intialize variable
// overflow
// go for easy solution
#define mod 1000000007
ll INF = 1000000000000000005LL;
//#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int arr[mxn],n;
int query(int x, int y){
    cout<<"? "<<x<<' '<<y<<endl;
    int val;
    cin>>val;
    return val;
}
void print(){
    cout<<"! ";
    for(int i=1;i<=n;i++){
        cout<<arr[i]<<' ';
    }
    cout<<endl;
}
int main(){
    rishabh();
    cin>>n;
    int prex, prey, pret;
    prex=prey=pret=0;
    for(int i=0;i<n;i++){
        int t,x,y;
        cin>>t>>x>>y;
        if(t-pret>=abs(x-prex)+abs(y-prey)&&((t-pret)%2==(abs(x-prex)+abs(y-prey))%2)){
            prex=x;
            prey=y;
            pret=t;
            continue;
        }
        else {
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)


void func(long long N, std::vector<long long> A){
    map<lli,lli> cnt;
    REP(i,0,N){
        cnt[-A[i]]++;
    }

    lli now=0;
    lli a[2];
    a[0]=0,a[1]=0;

    for(auto e:cnt){
        if(e.second>=4){
            if(now==0)a[0]=e.first;
            else a[1]=e.first;
            now++;
        }
        if(now>=2)break;
        if(e.second>=2){
            if(now==0)a[0]=e.first;
            else a[1]=e.first;
            now++;
        }
        if(now>=2)break;
    }
    cout<<a[0]*a[1]<<endl;
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    func(N, std::move(A));
    return 0;
}


Measured memory_bytes: 7296
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
int vis[10];
int check(int x)
{
    while(x)
    {
        int tmp=x%10;
        if(vis[tmp]) return 0;
        x/=10;
    }
    return 1;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        vis[x]=1;
    }
    for(int i=n;;i++)
    {
        if(check(i))
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
int main(){
    int N; std::cin >> N;
    for(int i = 0; i < N; ++i) {
        int a; std::cin >> a;
        if (a % 2) {
            std::cout << "first\n";
            return 0;
        }
    }
    std::cout << "second\n";
}

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

int main (void) {
  ll N, M;
  cin >> N >> M;
  ll ans = 0;
  if (M >= 2 * N) {
    ans = N;
    M -= 2 * N;
    ans += M / 4;
  } else {
    ans = M / 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;



int main() {
	string S, T;
	cin >> S >> T;
	int A = 0;
	
	if (S.at(0) == T.at(0)) {
		A++;
	}
	if (S.at(1) == T.at(1)) {
		A++;
	}
	if (S.at(2) == T.at(2)) {
		A++;
	}
	cout << A << endl;


	
}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int>av(m+1,1);
    vector<int>ttl(m+1,0);
    vector<vector<int> >mtx(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cin>>mtx[i][j];
    }
    int ans=n;

    for(int i=0;i<m;i++){
        for(int j=1;j<=m;j++){
            ttl[j]=0;

        }
        for(int j=0;j<n;j++){
            int k=0;
            while(!av[mtx[j][k]]) k++;
            ttl[mtx[j][k]]++;
        }

        int mxi=0;
        for(int j=1;j<=m;j++){
            ///cout<<ttl[j]<<' ';
            if(ttl[j]>ttl[mxi]){
                mxi=j;
            }
        }
        ans=min(ans,ttl[mxi]);
        ///cout<<ans<<'\n';
        av[mxi]=0;
    }

    cout<<ans<<'\n';
    return 0;
}
/**
5 3
0 2 1 4 3
4 4
0 1 2 3

10 4
2 0 1 3 7 5 4 6 8 9
*/


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

using namespace std;

const int N = 510;

int ans[N*N];

int main(){
	int n;
	cin >> n;
	
	vector <int> v(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v[i]);
		v[i]--;
	}


	vector <pair<int, int> > vz; // pos, val
	for (int i = 0; i < n; ++i) {
		vz.push_back(make_pair(v[i], i+1));
		ans[v[i]] = i+1;
	}

	sort(vz.begin(), vz.end());
	int nn = vz.size();
	for (int i = 0; i < nn; ++i) {
		int cnt = vz[i].second - 1;
		for (int k = 0; k < n*n; ++k) {
			if(ans[k] == 0 && k < vz[i].first && cnt) { // k < vz[i].first
				ans[k] = vz[i].second;
				cnt--;
			}	
		}
	}



	reverse(vz.begin(), vz.end());

	for (int i = 0; i < nn; ++i) {
		int cnt = n - vz[i].second;
		for (int k = n*n-1; k >= 0; --k) {
			if(ans[k] == 0 && k > vz[i].first && cnt) { // k < vz[i].first
				ans[k] = vz[i].second;
				cnt--;
			}	
		}
	}
	int ok = 1;
	for (int i = 0; i < n*n; ++i) {
		if(ans[i] == 0) ok = 0;
	}
	if (ok) {
		puts("Yes");
		for (int i = 0; i < n*n; ++i) {
			printf("%d ", ans[i]);
		}
	printf("\n");
	}
	else puts("No");
	

}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  vvi bingo(3, vi(3));
  re(i, 3) {
    re(j, 3) {
      cin >> bingo[i][j];
    }
  }
  int n;
  cin >> n;
  vvi data(3, vi(3, 0));
  re(k, n) {
    int b;
    cin >> b;
    re(i, 3) {
      re(j, 3) {
        if(b == bingo[i][j]) {
          data[i][j] = 1;
        }
      }
    }
  }

  if  (data[0][0] + data[0][1] + data[0][2] == 3
    || data[1][0] + data[1][1] + data[1][2] == 3
    || data[2][0] + data[2][1] + data[2][2] == 3
    || data[0][0] + data[1][0] + data[2][0] == 3
    || data[0][1] + data[1][1] + data[2][1] == 3
    || data[0][2] + data[1][2] + data[2][2] == 3
    || data[0][0] + data[1][1] + data[2][2] == 3
    || data[0][2] + data[1][1] + data[2][0] == 3)
  {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e17;
const ll MOD = 1e9+7;

// https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
ll modPow(long long a, long long n) {
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}

ll comb(ll n, ll p) {
	if (p * 2 > n) p = n - p;
	if (p > n - p) p = n - p;
	ll a = 1, b = 1;
	for(int i=1; i< p+1; i++) {
		a = (a * (n - i + 1)) % MOD;
		b = (b * i) % MOD;
	}
	return a * (modPow(b, MOD - 2)) % MOD;
}

int main() {
    // input, ready
    string N;
    cin >> N;

    string ans = "No";
    for (auto s : N) {
      if (s=='7') ans="Yes";
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long


int main(){
	int a,b, i,j, j_limit, days = 0;
	std::cin >> a >> b;

	for(i=1;i<=a;i++){
		if(i==a)j_limit = (b<j)?b:12;
		else j_limit = 12;

		for(j=1;j<=j_limit;j++){
			if(i==j)days++;
		}
	}


	std::cout << days << std::endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <stdlib.h>
 
int main() {
  
  string B;
  cin >> B;
  
  vector<char>vec(B.size());
  for(int i=0;i<B.size();i++){
    vec.at(i)=B.at(i);
  }
  int count=99999;
    for(int i=2 ;i<B.size();i++){
 int  A=vec.at(i-2)- '0',B=vec.at(i-1)- '0',C=vec.at(i)- '0';
 int D;
D=100*A+10*B+C;
 D=abs(753-D);
count=min(D,count);
  }
  cout << count <<endl;
  
}

Measured memory_bytes: 3584
num_length = int(input())
num_array = [int(x) for x in input().split()]


def selectionsort(A, N):
    exchange_counter = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j

        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            exchange_counter += 1

    print(" ".join(map(str, A)))
    print(exchange_counter)

selectionsort(num_array, num_length)

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

int main(){
    ll k, res = 0;
    cin>>k;
    for(int i = 1; i<=k; i++){
        for(int j = 1; j<=k ; j++){
            for(int m = 1; m<=k ; m++){
                res += __gcd(i, (__gcd(j, m)));
            }
        }
    }
    cout<<res;
}

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

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

int main() {
  int a,b;
  cin >> a >> b;
  if((a*b)%2==1)cout << "Odd" << endl;
  else cout << "Even" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define hi cout<<'h'<<'i'<<'\n' 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    cin>>n;
    string s;
    cin>>s;
    if(n%2)cout<<"No";
    else
    {
        string a=s.substr(0,n/2);
        string b=s.substr(n/2,n/2);
        if(a==b)cout<<"Yes";
        else cout<<"No";
    }
    return 0;
}



Measured memory_bytes: 256
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
struct edge { int to, cost; };
struct state { int pos; long long cost; };
bool operator<(const state& s1, const state& s2) { return s1.cost > s2.cost; };
int N, M, S, T, a[200009], b[200009], c[200009]; vector<edge> g[100009];
vector<long long> shortest_path(int start) {
	vector<long long> res(N, 1LL << 60); res[start] = 0;
	priority_queue<state> que; que.push(state{ start, 0 });
	while (!que.empty()) {
		int pos = que.top().pos; que.pop();
		for (edge e : g[pos]) {
			if (res[e.to] > res[pos] + e.cost) {
				res[e.to] = res[pos] + e.cost;
				que.push(state{ e.to, res[e.to] });
			}
		}
	}
	return res;
}
vector<int> calc(int start, vector<long long> dist) {
	vector<int> res(N), p(N); res[start] = 1;
	for (int i = 0; i < N; i++) p[i] = i;
	sort(p.begin(), p.end(), [&](int i, int j) { return dist[i] < dist[j]; });
	for (int i = 1; i < N; i++) {
		for (edge e : g[p[i]]) {
			if (dist[e.to] + e.cost == dist[p[i]]) {
				res[p[i]] += res[e.to];
				if (res[p[i]] >= mod) res[p[i]] -= mod;
			}
		}
	}
	return res;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> M >> S >> T; S--, T--;
	for (int i = 0; i < M; i++) {
		cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--;
		g[a[i]].push_back(edge{ b[i], c[i] });
		g[b[i]].push_back(edge{ a[i], c[i] });
	}
	vector<long long> ds = shortest_path(S);
	vector<long long> dt = shortest_path(T);
	vector<int> cs = calc(S, ds);
	vector<int> ct = calc(T, dt);
	int ret = 0;
	for (int i = 0; i < N; i++) {
		if (ds[i] * 2 == ds[T] && dt[i] * 2 == ds[T]) {
			ret = (ret + 1LL * cs[i] * cs[i] % mod * ct[i] % mod * ct[i]) % mod;
		}
	}
	for (int i = 0; i < M; i++) {
		if (ds[a[i]] + dt[b[i]] + c[i] == ds[T] && ds[a[i]] * 2 < ds[T] && dt[b[i]] * 2 < ds[T]) {
			ret = (ret + 1LL * cs[a[i]] * cs[a[i]] % mod * ct[b[i]] % mod * ct[b[i]]) % mod;
		}
		if (ds[b[i]] + dt[a[i]] + c[i] == ds[T] && ds[b[i]] * 2 < ds[T] && dt[a[i]] * 2 < ds[T]) {
			ret = (ret + 1LL * cs[b[i]] * cs[b[i]] % mod * ct[a[i]] % mod * ct[a[i]]) % mod;
		}
	}
	cout << (1LL * cs[T] * cs[T] - ret + mod) % mod << '\n';
	return 0;
}

Measured memory_bytes: 15956
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)

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

    int n; cin >> n;
    int l[n]; rep(i,n) cin >> l[i];
    int lmax = 0, lsum = 0;
    rep(i,n){
        lmax = max(lmax, l[i]);
        lsum += l[i];
    }
    if(lsum > 2*lmax) cout << "Yes";
    else cout << "No";
    
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
	string S; cin >> S;

	vector<char> stack1;

	for (int i = 0; i < S.size(); i++)
	{
		if (i != 0 && stack1.empty())
		{
			goto Rabbit;
		}

		stack1.push_back(S[i]);

		if (stack1.size() >= 3)
		{
			int end = stack1.size() - 1;

			if (stack1[end - 2] == 'm' && stack1[end - 1] == 'e' && stack1[end] == 'w')
			{
				stack1.pop_back();
				stack1.pop_back();
				stack1.pop_back();
			}
		}
	}

	if (stack1.size() == 0)
	{
		goto Cat;
	}

Rabbit:;

	cout << "Rabbit" << endl; goto Exit;

Cat:;

	cout << "Cat" << endl;

Exit:;

	return 0;
}

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

string S;
int main(){
    cin >> S;
    if(S[0]!='A'){
        cout << "WA" << endl;
        return 0;
    }
    int cnt = 0;
    for(int i=1;i<S.size();i++){
        if(isupper(S[i])){
            if(S[i]!='C' || i==1 || i==S.size()-1){
                cout << "WA" << endl;
                return 0;
            }
            if(S[i]=='C') cnt++;
        }
    }
    if(cnt!=1){
        cout << "WA" << endl;
        return 0;
    }
    cout << "AC" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define N 100000000
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
typedef struct{
    int pos;
    int tic;
}Load;
Load queue[N];
int head,num;
void enqueue(int pos,int tic){
    if(num<N){
        queue[(head+num)%N].pos=pos;
        queue[(head+num)%N].tic=tic;
        num++;
    }else{
        printf("エラー\n");
        exit(1);
    }
}
Load dequeue(double cost[30][(1<<8)]){
    int index=head;
    int min=cost[queue[head].pos][queue[head].tic];
    for(int i=head+1;i<head+num;i++){
        if(min>cost[queue[i%N].pos][queue[i%N].tic]){
            min=cost[queue[i%N].pos][queue[i%N].tic];
            index=i%N;
        }
    }
    Load tmp=queue[head]; queue[head]=queue[index]; queue[index]=tmp;
    Load d={-1,-1};
    if(num>0){
        d=queue[head];
        head=(head+1)%N;
        num--;
    }
    return d;
}
int main(void){
    while(1){
        int n,m,p,a,b;
        int t[8];
        int load[30][30]={0};
        scanf("%d%d%d%d%d",&n,&m,&p,&a,&b);
        //初期化 1<=a,b<=n
        a--; b--;
        if(n==0) break;
        rep(i,n) scanf("%d",&t[i]);
        //rep(i,n) printf("%d ",t[i]); puts("");
        int x,y,z;
        rep(i,p){//隣接行列
            scanf("%d%d%d",&x,&y,&z);
            load[x-1][y-1]=load[y-1][x-1]=z;
        }
        /*rep(i,m) {
            rep(j,m){
                printf("%2d ",load[i][j]);
            }puts("");
        }puts("");*/
        head=num=0;
        enqueue(a,0);
        double cost[30][(1<<8)]={0};
        while(1){//ダイクストラ
            Load tmp=dequeue(cost);
            int pos=tmp.pos,tic=tmp.tic;
            if(pos==-1) break;
            if(pos==b) continue;
            for(int i=0;i<m;i++){
                if(load[pos][i]>0){
                    for(int j=0;j<n;j++){
                        if(!((tic>>j)&1)){
                            int ntic=(tic|(1<<j));
                            if(cost[i][ntic]==0||cost[i][ntic]>
                               (cost[pos][tic]+(1.0*load[pos][i]/t[j]))){
                                cost[i][ntic]=cost[pos][tic]
                                +(1.0*load[pos][i]/t[j]);
                                enqueue(i,ntic);
                            }
                        }
                    }
                }
            }
        }
        double min=N;
        //ミス
        for(int i=0;i<(1<<n);i++){
            if(cost[b][i]!=0&&min>cost[b][i])
                min=cost[b][i];
        }
        if(min==N) printf("Impossible\n");
        else printf("%f\n",min);
    }
}



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

int main() {
	string s1, s2, s3;
	cin >> s1 >> s2 >>s3;
	char c1, c2, c3;
	c1 = s1.at(0) - 32;
	c2 = s2.at(0) - 32;
	c3 = s3.at(0) - 32;
	cout << c1 << c2 << c3 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using P = pair<int, int>;

constexpr int INF = 1e9;

int main() {
    int R, C, M;
    cin >> R >> C >> M;
    vector<string> v(R);
    for(int i=0; i<R; ++i) {
        cin >> v[i];
    }
    // 0: per, 1: on, 2: off
    vector<vector<vector<int>>> cost(3, vector<vector<int>>(R, vector<int>(C)));
    for(int i=0; i<3; ++i) {
        for(int j=0; j<R; ++j) {
            for(int k=0; k<C; ++k) {
                cin >> cost[i][j][k];
            }
        }
    }
    vector<P> task(M);
    for(int i=0; i<M; ++i) {
        cin >> task[i].first >> task[i].second;
    }
    int res = cost[1][task[0].first][task[0].second] + cost[2][task[0].first][task[0].second];
    vector<vector<int>> prev_t(R, vector<int>(C, INF));
    prev_t[task[0].first][task[0].second] = 0;
    int t = 0;
    for(int i=1; i<M; ++i) {
        queue<P> que;
        que.push(task[i-1]);
        vector<vector<int>> d(R, vector<int>(C, INF));
        vector<vector<P>> prev(R, vector<P>(C, P{-1, -1}));
        d[task[i-1].first][task[i-1].second] = t;
        while(!que.empty()) {
            P p = que.front(); que.pop();
            int dr[4] = {0, 1, 0, -1},
                dc[4] = {1, 0, -1, 0};
            for(int j=0; j<4; ++j) {
                int nr = p.first + dr[j],
                    nc = p.second + dc[j];
                if(nr < 0 || R <= nr || nc < 0 || C <= nc || v[nr][nc] == '#') {
                    continue;
                }
                if(d[nr][nc] == INF) {
                    d[nr][nc] = d[p.first][p.second] + 1;
                    prev[nr][nc] = p;
                    que.push(make_pair(nr, nc));
                }
            }
        }
        int r = task[i].first, c = task[i].second;
        t = d[r][c];
        while(r != task[i-1].first || c != task[i-1].second) {
            if(prev_t[r][c] != INF) {
                res += min((d[r][c] - prev_t[r][c]) * cost[0][r][c], cost[1][r][c] + cost[2][r][c]);
            } else {
                res += cost[1][r][c] + cost[2][r][c];
            }
            prev_t[r][c] = d[r][c];
            P p = prev[r][c];
            r = p.first, c = p.second;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3240
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			String str = scan.nextLine();
			if(str.equals(".")){
				break;
			}
			char[] sta = new char[100];
			int sp = 0;
			boolean sw = false;
			for(int i = 0;i < str.length();i++){
				switch(str.charAt(i)){
				case '(':
					sta[sp++] = '(';
					break;
				case '[':
					sta[sp++] = '[';
					break;
				case ')':
				    if(sp == 0){
				    	sw = true;
				    }else if(sta[--sp] == '('){
					}else{
						sw = true;
					}
					break;
				case ']':
					if(sp == 0){
				    	sw = true;
				    }else if(sta[--sp] == '['){
					}else{
						sw = true;
					}
					break;
					default:
						break;
				}
				if(sw){
					break;
				}
			}
			if(sw){
				System.out.println("no");
			}else{
				System.out.println((sp == 0)?"yes":"no");
			}
		}
	}
}

Measured memory_bytes: 33340
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    multimap<int, int> mm;
    for(;;){
        int a, b;
        char c;
        cin >> a >> c >> b;
        if(a == 0 && b == 0)
            break;
        mm.insert(make_pair(30-b, a));
    }

    for(;;){
        int a;
        if(!(cin >> a))
            return 0;

        int rank = 0;
        int score = -1;
        multimap<int, int>::iterator it;
        for(it = mm.begin(); ; ++it){
            if(it->first != score){
                score = it->first;
                ++ rank;
            }
            if(it->second == a){
                cout << rank << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 712
#include <stdio.h>
#define rep(i,l,r) for((i)=(l);(i)<(r);(i)++)
int main(){
    int i,n,ans=0;
    scanf("%d",&n);
    int v[n],c;
    rep(i,0,n)scanf("%d",&v[i]);
    rep(i,0,n){
        scanf("%d",&c);
        if(v[i]>c)ans+=v[i]-c;
    }
    printf("%d",ans);
}

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

using namespace std;

int32_t main() {
  char X, Y;
  cin >> X >> Y;
  if (X == Y) {
    cout << "=" << endl;
  } else if (X < Y) {
    cout << "<" << endl;
  } else {
    cout << ">" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

int main() {
	IN(string, s);
	IN(int, Q);
	
	deque<char> d;
	RF(e, s) { d.PB(e); }
	
	int x = 0;
	inc(q, Q) {
		IN(int, t);
		if(t == 1) { x ^= 1; }
		if(t == 2) {
			IN(int, f);
			IN(string, c);
			f--;
			if(x == f) { d.push_front(c[0]); }
			if(x != f) { d.push_back (c[0]); }
		}
	}
	
	s = "";
	RF(e, d) { s.PB(e); }
	if(x == 1) { reverse(ALL(s)); }
	OUT(s);
}


Measured memory_bytes: 1280
#include<stdio.h>
int main(){
  int i,j,k,n,x;
  int a;

  while(1){
    scanf("%d %d",&n,&x);

    if(n==0&&x==0)break;
    (a=0);
    for(i=1;i<=n;i++){
      for(j=2;j<=n;j++){
	for(k=3;k<=n;k++){
	  if(i+j+k==x){
	    (a++);
	    if(i>=j||j>=k||i==k){
	      (a--);
	    }
	  }
	}
      }
    }
    printf("%d\n",a);
  }
  return 0;
}

Measured memory_bytes: 1028
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <queue>
#include <sstream>
#include <unordered_map>
#include <cstring>
#include <iomanip>

using namespace std;

typedef long long ll;

const ll INF=1e9+7;

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

#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
    int N,K,count=0;
    cin>>N>>K;
    int A[N];
    rep(i,N){
        int a;
        cin>>a;
        if(K<=a) count++;
    }
    cout<<count<<endl;
    return 0;
}

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

int  main(void){
  int a=0;
  int b=0;
  int c=0;
  int per=0;
  int max=0;
  int sec;
  int third;
  cin>>a>>b>>c>>per;
  if(a>=b)
  {
    max=a;
    sec=b;
    if(a<=c)
    {
      max=c;
      sec=a;
      third=b;
    }
    else{
    if(b<=c)
    {
    sec=c;
    third=b;
    }
    else
    third=c;
  }
}
  else
  {
   max=b;
   sec=a;
   if(b<=c)
   {
     max=c;
     sec=b;
     third=c;
   }
   else{
   if(a<=c){
   sec=c;
   third=a;
 }else third=c;
  }
}
for(int i=0;i<per;i++)
{
  max=max*2;
}
int sum=max+sec+third;
cout<<sum<<endl;
return 0;
}


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

using namespace std;

const int N = 200010;

int n, m;
int p[N], cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int sz[N];
bool st[N];
int main()
{
  string s,t;
   cin >> s;
  cin >> t;
  int ans = 1e9;
 int sl = s.length();
  int tl = t.length();
  int i,j;
  for(i=0; i < sl; i++)
  {
    int k = 0;
    bool b = true;
  	for(j=0; j < tl; j++)
    {
    	if((i+j) < sl && t[j] != s[i+j])
          	k++;
      	if(i+j >= sl)
          	b = false;
    }
    if(b)
    	ans = min(ans,k);
  }
  cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3608
//#include <bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<iterator>
#include<algorithm>
#include<bitset>

#define Filein(N) freopen("N", "r", stdin);
#define Fileout(N) freopen("N", "w", stdout);
#define sci(x) scanf("%d", &x)
#define sci2(x,y) scanf("%d%d", &x,&y)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll(x) scanf("%lld",&x)
#define scd(x) scanf("%lf", &x)
#define scstr(x) scanf("%s", x)
#define pfi(x) printf("%d", x)
#define pfll(x) printf("%lld", x)
#define pfd(x) printf("%f", x)
#define pfstr(x) printf("%s", x)
#define ps printf(" ")
#define pn printf("\n")
#define pfdt printf("..")

#define For(var,start,end) for(int var=start; var<=end;i++)
#define rFor(var,start,end) for(int var=start; var>=end; i--)
#define TestCase int testcase, cs=1; cin>>testcase;while(testcase--)

#define mkp make_pair
#define pb push_back
#define fi first
#define se second

#define px(x) cout<<"X -> "<<x<<endl;
#define py(x) cout<<"Y = "<<x<<endl;
#define pz(x) cout<<"Z >> "<<x<<endl;
#define pstr(x) printf("%s\n",x);

using namespace std;
using ll = long long;
using vi = vector <int>;
using mpii = map<int,int>;
using si = set<int>;
using sll = set<ll>;
using vll= vector<ll>;

#define INF 1000000000
#define LINF 4000000000000000000
#define pi  (2*acos(0))
#define Mod 1000000007

 int main(){
 char str[1000000],str2[1000000];

 scstr(str);
 scstr(str2);

 int sz = strlen(str),cnt=0;
  For(i,0,sz-1){
   if(str[i]!=str2[i]) cnt++;

  }
  pfi(cnt);

    return 0;
}







Measured memory_bytes: 4208
#include <bits/stdc++.h>
using namespace std;
						
#define fast_cin() ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long
				
int32_t main() {
	fast_cin();  
	int n; cin >> n;
	int total = n * ((n * (n + 1) / 2))- ((n * (n + 1) * (2 * n + 1)) / 6 - (n * (n + 1)) / 2);
	for (int i = 0; i < n - 1; ++i) {
		int u, v; cin >> u >> v;
		if (u > v) swap(u, v);
		total -= u * (n - v + 1);
	}
	cout << total << endl;
	return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll a; ll b; ll c; ll k;
    cin >> a >> b >> c >> k;
    ll ans = 0;
    ans += min(a, k);
    k -= min(a, k);
    k -= min(b, k);
    ans -= min(c, k);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(){
    int W,H,x,y,r;
    scanf("%d",&W);
    scanf("%d",&H);
    scanf("%d",&x);
    scanf("%d",&y);
    scanf("%d",&r);
    if((r<=x&&x<=W-r)&&(r<=y&&y<=H-r)){
        printf("Yes");
    }else{
        printf("No");
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin >>N;
  vector<int> A(N);
  for (int i=0;i<N;i++){
    cin>>A.at(i);
  }
  sort(A.begin(),A.end());
  for (int i=1;i<N;i++){
    if(A.at(i)==A.at(i-1)){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
  return 0;
}

Measured memory_bytes: 1024
n,m=map(int,input().split())
x=list(map(int,input().split()))

memo=[n+1 for _ in range(n+1)]
memo[n]=0

for i in range(n,-1,-1):
    for xx in x:
        if i-xx<0:
            continue
        memo[i-xx]=min(memo[i-xx],memo[i]+1)
print(memo[0])


Measured memory_bytes: 7636
#include <bits/stdc++.h>
#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 ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string a,b;
  cin >> a >> b;
  if(a.size()<b.size()) puts("LESS");
  else if(a.size()>b.size()) puts("GREATER");
  else{
    if(a<b) puts("LESS");
    else if(a>b) puts("GREATER");
    else puts("EQUAL");
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int x,y;
  cin >> x >> y;
  if( y >= 2*x && y <= 4*x){
    if(y % 2 == 0) cout << "Yes";
    else cout << "No";
  }
  else cout << "No";
  
  return 0;
  
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

struct UnionFind
{
  vector<int> d;
  UnionFind(int n = 0) : d(n, -1) {}
  int find(int x)
  {
    if (d[x] < 0)
      return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if (x == y)
      return false;
    if (d[x] > d[y])
      swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};

int main()
{
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i, H)
  {
    cin >> S[i];
  }
  UnionFind uf(H * W);
  rep(h, H) rep(w, W)
  {
    int dirh[] = {1, -1, 0, 0};
    int dirw[] = {0, 0, 1, -1};
    rep(i, 4)
    {
      int next_h = h + dirh[i];
      int next_w = w + dirw[i];

      if (0 <= next_h && next_h < H && 0 <= next_w && next_w < W && S[next_h][next_w] != S[h][w])
      {
        int index = h * W + w;
        int next_index = next_h * W + next_w;
        uf.unite(index, next_index);
      }
    }
  }
  vector<pair<long long, long long>> count(H * W);
  rep(h, H) rep(w, W)
  {
    int index = h * W + w;
    index = uf.find(index);
    if (S[h][w] == '.')
      count[index].first++;
    else
      count[index].second++;
  }
  long long ans = 0;
  rep(i, H * W)
  {
    ans += count[i].first * count[i].second;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3712
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

# input
lpre = nil
l = $stdin.gets

input = []
while l = $stdin.gets do
  lcur = l.to_i
  next if lpre == lcur
  input << lcur
  lpre = lcur
end

hh = {}
dp = []
input.size.times do |i|
  if i == 0
    dp[i] = 1
    hh[input[i]] = 1
    next
  end
  if hh[input[i]] == nil
    dp[i] = dp[i-1]
    hh[input[i]] = dp[i]
  else
    dp[i] = dp[i-1] + hh[input[i]]
    hh[input[i]] = dp[i]
  end
end

puts dp[-1] % (10**9 + 7)


Measured memory_bytes: 716796
use std::cmp::max;
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn gcd(a: i32, b: i32) -> i32 {
    fn gcd1(m: i32, n: i32) -> i32 {
        if n == 0 {
            m
        } else {
            gcd1(n, m % n)
        }
    }
    if a > b {
        gcd1(a, b)
    } else {
        gcd1(b, a)
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut av = vec![0i32; n];
    for i in 0..n - 1 {
        av[i] = read(&mut stdin_lock, &mut buf, b' ');
    }
    av[n - 1] = read(&mut stdin_lock, &mut buf, b'\n');

    let mut lv = vec![0i32; n];
    lv[0] = av[0];
    for i in 1..n {
        lv[i] = gcd(lv[i - 1], av[i]);
    }
    let mut rv = vec![0i32; n];
    rv[n - 1] = av[n - 1];
    for i in 1..n {
        let j = n - i - 1;
        rv[j] = gcd(rv[j + 1], av[j]);
    }

    let mut ans = max(gcd(av[1], rv[1]), gcd(lv[n - 2], av[n - 2]));
    for i in 1..n - 1 {
        ans = max(ans, gcd(lv[i - 1], rv[i + 1]));
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
while True:
  a,op,b = input().split()
  a=int(a)
  b=int(b)
  if op=='?':
    break
  if op=='+':
   print(a+b)
  if op=='-':
   print(a-b)
  if op=='*':
   print(a*b)
  if op=='/':
   print(a//b)



Measured memory_bytes: 5592
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;
using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;
using VS = vector< string >;
using SS = stringstream;
using PII = pair< int, int >;
using VPII = vector< pair< int, int > >;
template < typename T = int > using VT = vector< T >;
template < typename T = int > using VVT = vector< vector< T > >;
template < typename T = int > using LIM = numeric_limits< T >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

#define NUMBERED( name, number ) NUMBERED2( name, number )
#define NUMBERED2( name, number ) name ## _ ## number
#define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n )
#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &&e : c )
#define ALL( c ) begin( c ), end( c )
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

template < typename T > inline bool chmin( T &a, const T &b ){ if ( b < a ) { a = b; return true; } return false; }
template < typename T > inline bool chmax( T &a, const T &b ){ if ( a < b ) { a = b; return true; } return false; }

#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

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

	int N;
	scanf( "%d", &N );

	VI A( N );
	for_each( ALL( A ), []( int &a ){ scanf( "%d", &a ); } );

	LL res = A[0] - 1;
	int p = 2;
	REP( i, 1, N )
	{
		int &a = A[i];
		if ( a == p )
		{
			++p;
			continue;
		}
		res += ( a - 1 ) / p;
	}

	printf( "%lld\n", res );
	fflush( stdout );

	return 0;
}


Measured memory_bytes: 768
#include<stdio.h>

void visit(int);
int map[101][101];
int f[101],d[101],color[101],time,n;
int main()
{
  int i,j,v,vv,m;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    color[i]=0;
    for(j=0;j<n;j++){
      map[i][j]=0;
    }
  }
  time=0;
  for(i=0;i<n;i++){
    scanf("%d%d",&v,&m);
    for(j=0;j<m;j++){
      scanf("%d",&vv);
      map[v-1][vv-1]=1;
    }
  }
  for(i=0;i<n;i++){
    if(color[i]==0)visit(i);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
  return 0;
}

void visit(int u)
{
  int i;
  color[u]=1;
  d[u]=++time;
  for(i=0;i<n;i++){
    if(map[u][i]==1){
      if(color[i]==0)visit(i);

    }
  }
  color[u]=2;
  f[u]=++time;
  }



Measured memory_bytes: 2140
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")] * 10 ** 6
h = h + [0] * 10 ** 6
dp[0] = 0
for i in range(N):
    for j in range(1, K + 1):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[N - 1])

Measured memory_bytes: 95200
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;

const LL mod = 1e9 + 7;
const int maxn = 1e5 + 5;

LL fac[maxn];

void init(){
	fac[0] = 1;
	for(int i = 1;i <= 100000;i++){
		fac[i] = fac[i - 1] * i % mod;
	}
}
int n;
int x[maxn];

int main(){
	init();
	while(scanf("%d",&n) != EOF){
		for(int i = 1;i <= n;i++){
			scanf("%d",&x[i]);
		}
		int k = 0;
		LL ans = 1;
		for(int i = 1;i <= n;i++){
			if(x[i] >= 2 * k + 1){
				k++;
			}else{
				ans = ans * (k + 1) % mod;
			}
		}
		ans = ans * fac[k] % mod;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 1408
#encoding:utf-8 No.0033 2014.10.7
n = gets.chomp.to_i
cylinderA = Array.new(n)
judgement = Array.new(n)

n.times do |i|
  cylinderA[i] = gets.chomp.split.map{|item| item.to_i}
  cylinderB = []
  cylinderC = []
  
  cylinderB.push cylinderA[i][0] #まずひとつcylinderBに入れる
  j = 1
  while j < cylinderA[i].length  #cylinderAからひとつずつ落としていく
    if cylinderA[i][j] > cylinderB.last
      cylinderB.push cylinderA[i][j]  #cylinderBには確実に昇順に並ぶ
    else
      cylinderC.push cylinderA[i][j]  #cylinderCには昇順に並ぶとは限らない
    end
    j += 1
  end
  
  if cylinderC == cylinderC.sort
    judgement[i] ="YES"
  else
    judgement[i] ="NO"
  end
end

puts judgement

Measured memory_bytes: 6108
#include <bits/stdc++.h>
#define ll long long
#define EPS 1e-9
#define rank asadf
using namespace std;

const int MAXN = 3e5 + 111;
const int MOD = 1e9 + 7;



int main() {
#ifdef LOCAL
    freopen("xxx.in", "r", stdin);
    freopen("xxx.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        sum += (s[i] - '0');
    }
    cout << (sum % 9 == 0 ? "Yes\n" : "No\n");
    return 0;
}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
typedef long long ll;
const int MOD = 1000000007;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x;
  cin >> x;
  
  if(x == 7 || x == 5 || x == 3){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}



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

int main(){
  int K, X;
  scanf("%d %d", &K, &X);

  if(K < 1 || K > 100 || X < 0 || X > 100)
    return 1;

  for(int i = X - K + 1; i < X + K; i++)
    printf("%d ", i);

}

Measured memory_bytes: 256
// AtCoder Regular Contest 080
// E - Young Maids

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, pii> piii;


const int MAX_N = 200000;
const int MAX_ELEMENTS = 1 << 17;
const int INF = (int)1e8;

template <typename T>
class SegmentTree {
public:
  int n;
  T dat[2 * MAX_ELEMENTS - 1];
  void init(int _n);
  void update(int k, T a);
  T query(int a, int b);
private:
  T query(int a, int b, int k, int l, int r);
};

template <typename T>
void SegmentTree<T>::init(int _n) {
  n = 1;
  while (n < _n) {
    n <<= 1;
  }
  for (int i = 0; i < 2 * n - 1; i++) {
    dat[i] = INF;
  }
  return;
}

template <typename T>
void SegmentTree<T>::update(int k, T a) {
  k += n - 1;
  dat[k] = a;
  while (k > 0) {
    k = (k - 1) / 2;
    dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
  }
  return;
}

template <typename T>
T SegmentTree<T>::query(int a, int b) {
  return query(a, b, 0, 0, n);
}

// [a, b), [l, r)
template <typename T>
T SegmentTree<T>::query(int a, int b, int k, int l, int r) {
  if (r <= a || b <= l) {
    return INF;
  }
  if (a <= l && r <= b) {
    return dat[k];
  }
  return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
}


int N;
int p[MAX_N];
int at[MAX_N + 1];
SegmentTree<int> st[2];
priority_queue<piii, vector<piii>, greater<piii>> q;
vector<int> ans;

int main() {

    int l, r, a, b, av, bv;

    cin >> N;
    st[0].init(N / 2);
    st[1].init(N / 2);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        at[p[i]] = i;
        st[i % 2].update(i / 2, p[i]);
    }

    q.push(piii(st[0].query(0, N / 2), pii(0, N)));
    while (!q.empty()) {
        piii sec = q.top(); q.pop();
        l = sec.second.first;
        r = sec.second.second;
        if (l >= r) {
            continue;
        }
        av = sec.first;
        a = at[av];
        bv = st[(l + 1) % 2].query((a + 1) / 2, (r + 1) / 2);
        b = at[bv];
        ans.push_back(av); ans.push_back(bv);
        q.push(piii(st[l % 2].query(l / 2, a / 2), pii(l, a)));
        q.push(piii(st[(a + 1) % 2].query((a + 1) / 2, b / 2), pii(a + 1, b)));
        q.push(piii(st[(b + 1) % 2].query((b + 1) / 2, r / 2), pii(b + 1, r)));
    }

    for (int i = 0; i < N; i++) {
        cout << ans[i] << (i == N - 1 ? '\n' : ' ');
    }

    return 0;

}





Measured memory_bytes: 9776