akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>

using namespace std;
typedef long long ll;

struct UnionFind {
    vector<int> parent;
    UnionFind (int n) : parent(n) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int root (int x) {
        if(parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    void unite(int x, int y) {
        int root_x = root(x);
        int root_y = root(y);
        if(root_x == root_y) return;

        parent[root_x] = root_y;
    }

    bool same_root (int x, int y) {
        int root_x = root(x);
        int root_y = root(y);
        return root_x == root_y;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }
    
    UnionFind tree(n);
    for (int i = 0; i < m; i++)
    {
        int x, y; cin >> x >> y;
        x--; y--;
        tree.unite(x, y);
    }
    
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if(tree.same_root(i, p[i])) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int wantToEat[3];
    int grapes[3];
    int friends[3] = {0};
    bool pass = true;
//    for (int i = 0; i<3; i++){
//        cin>> wantToEat[i];
//    }
//    for (int i = 0; i< 3; i++){
//        cin>> grapes[i];
//    }
//    for (int i = 0; i< 3; i++){ //i is the specific (friend's) want
//        for (int j = 0; j< i; j++){// j is the type of grape
//            cout<< j<< " ";
//            while (grapes[j]>0 ){
//                if (friends[i]< wantToEat[i]){
//                    grapes[i]--;
//                    friends[i]++;
//                }
//                else {
//                    break;
//                }
//            }
//        }
//    }
//    //check validity
//    for (int i = 0; i< 3; i++){
//        cout << friends[i]<< " ";
//        if (friends[i]<wantToEat[i]){
//            pass = false;
//        }
//    }
//    if (pass){
//        cout << "YES";
//    }
//    else {
//        cout << "NO";
//    }
    
//    //thelimit exceeded
    int n, t;
    int m = 10000;
    cin>> n>> t;
    int routes[n][2];
    for (int i = 0; i< n; i++){
        for (int j = 0; j< 2; j++){
            cin>> routes[i][j];
        }
    }
    for (int i = 0; i< n; i++){
        if (routes[i][1]<= t ){ // if it under the time
            if (routes[i][0]< m){
                m = routes[i][0];
            }
        }
    }
    if (m==10000){
        cout << "TLE";
    }
    else{
        cout << m;
    }
    //delete from the left
    
    
    
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int r, d, x;
  std::cin >> r >> d >> x;
  for (int i = 0; i < 10; ++i) {
    x = x * r - d;
    std::cout << x << std::endl;
  }
  return 0;
}


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

#define ll long long 
#define pll pair<ll,ll> 

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n;
	cin>>n;
	ll A[n];
	for(ll i=0;i<n;i++)
		cin>>A[i];
	
	ll ans=0;
	for(ll i=1;i<n;i++){
		if(A[i]<A[i-1]){
			ans+=A[i-1]-A[i];
			A[i]=A[i-1];
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 5160
#include <stdio.h>
int main()
{
    int n, m, ans = 0;

    scanf("%d %d", &n, &m);

    if(n > 1) ans += n * (n - 1) / 2;
    if(m > 1) ans += m * (m - 1) / 2;

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

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;

int w[110];

int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   int n; 
   int ans = 1e9;
   cin >> n;
   for(int i = 0 ; i < n ;i++) cin >> w[i];
   for(int t = 0 ; t < n - 1; t++){
      int sum1 = 0, sum2 = 0;
      for(int i = 0 ; i <= t ; i++) sum1 += w[i];
      for(int i = t + 1 ; i < n ; i++) sum2 += w[i];
      ans = min(ans,abs(sum1-sum2));
   }    
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
      int2(h, w);
      string s;
      rep(i, h)rep(j, w){
        cin >> s;
        if(s == "snuke"){
          printf("%c%d\n", 'A' + j, i + 1);
          break;
        }
      }



/*/

//*/ break;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

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

        for (int i = 0; i < n; i++){
            numberArray[i] = sc.nextInt();
        }

        int count = 0;

        for (int i = 0; i  < n; i++){
            for (int j = n -1; j > 0; j --){
                int rightInt = numberArray[j];
                int leftInt = numberArray[j - 1];
                if(rightInt < leftInt){
                    numberArray[j] = leftInt;
                    numberArray[j - 1] = rightInt;
                    count++;
                }
            }
        }

        // Array出力
        StringJoiner sj = new StringJoiner(" ");
        Arrays.stream(numberArray).forEach(i -> sj.add(String.valueOf(i)));
        System.out.println(sj.toString()); // => 1,2,3,4,5

        System.out.println(count);



    }

}


Measured memory_bytes: 32312
n=int(input())
a=list(map(int,input().split()))
x=1
c=0
if a.count(0)>0:
    print(0)
else:
    for i in range(n):
        x=x*a[i]

        if x>10**18:
            print(-1)
            c=1
            break        

        
    if c==0:
        print(x)

Measured memory_bytes: 21580
n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
b=list(map(int,input().split()))
b.insert(0,0)
c=list(map(int,input().split()))
c.insert(0,0)
ans=b[a[1]]
for i in range(2,n+1):
    ans+=b[a[i]]
    if a[i]-a[i-1]==1:
        ans+=c[a[i-1]]
print(ans)

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

typedef long long ll;
using namespace std;

#define REP(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define sum(v) accumulate(ALL(v),0)

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<" ";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k, x;
    cin>>k>>x;
    //想定範囲はx-(k-1)からx+(k-1)
    if(x-(k-1)<=-100000){
        rep(i,k){
            cout << -100000+i << " ";
        }
    }else if(x+(k-1)>=100000){
        rep(i,k){
            cout << 100000-(k+1)+i << " ";
        }
    }else{
        rep(i,2*k-1){
            cout << x-k+1+i << " ";
        }
    }
    return  0;
}


Measured memory_bytes: 256
#include<cstdio>
typedef long long ll;
const int M=1000000007;
ll a,b;
ll abs(ll x){
	return x>0?x:-x;
}
ll fac(ll x){
	ll s=1;
	for(ll i=1;i<=x;i++)
		s=s*i%M;
	return s;
}
int main(){
	scanf("%lld%lld",&a,&b);
	if(abs(a-b)>1)
		printf("0");
	else
		if(a==b)
			printf("%lld",fac(a)*fac(b)*2%M);
		else
			printf("%lld",fac(a)*fac(b)%M);
}

Measured memory_bytes: 128
N = int(input())
*A, = map(int, input().split())

MOD = 10**9 + 7

S = [0]*(N+1)
r = 0
for i in range(1, N+1):
    S[i] = r = (r + pow(i, MOD-2, MOD)) % MOD

ans = 0
for i in range(N):
    ans += A[i] * (S[i+1] + S[N-i] - 1)
for i in range(1, N+1):
    ans = ans * i % MOD
print(ans)

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

int main() {
  int n, sum = 0;
  cin >> n;
  
  vector<int> an(n+2);
  rep(i, n) {
    cin >> an[i+1];
    sum += abs(an[i+1] - an[i]);
  }
  sum += abs(an[n]);
  
  vector<int> bn(n);
  rep(i, n) {
    int s;
    s = sum 
      - abs(an[i] - an[i+1]) 
      - abs(an[i+1] - an[i+2])
      + abs(an[i] - an[i+2]);
    cout << s << endl;
  }
  
}


Measured memory_bytes: 2048
#include <stdio.h>
#include <iostream>
#include <stdlib.h>

int main() {
  int    input, odd = 0;
  double output;

  std::cin >> input;
  if(input == 0) {
  std::cout << 0 << std::endl;
  return 0;
  }
  for(int i = 1; i <= input; i++) {
    if(i % 2 != 0) {
      odd += 1;
    }
  }
  output = (double)odd / input;
  //  std::cout << odd << std::endl;                                                                                                                                                                        
  std::cout << output << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>

int main()
{
	int k,s,ans=0;

	scanf("%d %d",&k,&s);

	int n[2*k+1]={0};

	for(int i=0;i<k+1;i++){
		for(int j=0;j<k+1;j++){
			n[i+j]++;
		}
	}

	for(int i=0;i<k+1;i++){
		if(s-i>=0 && s-i<=2*k) ans+=n[s-i];
	}

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

	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long;
int dp[100009];
int val[100009];
int n,k;
int frog(int i)
{
    if(i==n-1)return 0;
    if(i>n-1)return 9898981;
   // cout<<"I = "<<i<<endl;

//    if(i==n-1)return (abs(val[i]-val[n-1]));
//    if(i==n-2)return (abs(val[i]-val[n-2]));
    if(dp[i]!=-1)return dp[i];
    int ans=INT_MAX;
    for(int j=1;j<=k;j++)
    {
        int data=frog(i+j)+abs(val[i]-val[i+j]);
        if(ans>data)
            ans=data;
        //cout<<"return value = "<<data<<"  min value = "<<ans<<endl;
    }
    dp[i]=ans;
    return dp[i];
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int d;cin>>d;
        val[i]=d;
    }
    memset(dp,-1,sizeof(dp));
    int ans=frog(0);
    cout<<ans<<endl;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
typedef pair<int, int> pint;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, a;
    while(cin >> n >> m >> a && n){
        vector<int> tate(n);
        rep(i, n) tate[i] = i;
        multimap<int, pint> yoko;
        rep(i, m){
            int h, p, q;
            cin >> h >> p >> q;
            p--; q--;
            yoko.insert(make_pair(h, pint(p, q)));
        }
        for(const auto& k : yoko){
            pint temp = k.second;
            swap(tate[temp.first], tate[temp.second]);
        }
        cout << tate[a - 1] + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3172
#include <iostream>
using namespace std;
int main(){
  int a[7];
  int b[7];
  for(int i=0;i<7;i++){
    cin >>a[i]>>b[i];
  }

  for(int i=0;i<7;i++){
    cout <<a[i]-b[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 3088
N=int(input())
s=input()

def _rot_n(c, n):
    if 'A' <=c and c <='Z':
        return chr((ord(c)-ord('A') + n) % 26 + ord('A'))
    return c

def rot_n(s, n):
    g = (_rot_n(c, n) for c in s)
    return ''.join(g)

s = rot_n(s, N)
print(s)


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

int main() {
	
	int n;
	cin >> n;
	vector<int> h(n), zero(n, 0);
	rep(i, n) cin >> h[i];
	
	int ans = 0;
	
	while(h != zero){
		int p = 0;
		while(h[p] == 0){
			p++;
		}
		while(h[p] != 0 && p < n){
			h[p]--;
			p++;
		}
		// rep(i, n) cout << h[i] << " ";
		// cout << endl;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.Scanner;

class Main
{
	public static void main(String[] args) throws Exception
	{
		invoke(System.in);
	}

	public static void	invoke(InputStream is) throws IOException
	{
		try (Scanner in = new Scanner(is))
		{
			String	s = in.next();
			System.out.println("2018" + s.substring(4));
		}
	}
}

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

int main(){
    int n;
    cin >> n;
    vector<int> dp(n+1);
    dp.at(0)=0;
    for(int i=1; i<n+1; i++){
        dp.at(i) = dp.at(i-1)+1;
        int k=6;
        while(k<=i){
            dp.at(i) = min(dp.at(i),dp.at(i-k)+1);
            k*=6;
        }
        k=9;
        while(k<=i){
            dp.at(i) = min(dp.at(i), dp.at(i-k)+1);
            k*=9;
        }
    }
    cout << dp.at(n) << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> ga[100010];
int a,b;
int indeg[100010],ancest[100010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=(n-1+m);i++){
		cin>>a>>b;
		ga[a].push_back(b);
		indeg[b]++;
	}
	stack<int> s;
	for(int i=1;i<=n;i++)
	   if(indeg[i]==0)
	      s.push(i);
	while(!s.empty()){
		int p=s.top();
		s.pop();
		for(int i=0;i<ga[p].size();i++){
			int to=ga[p][i];
			indeg[to]--;
			if(indeg[to]==0){
				s.push(to);
				ancest[to]=p;
			}
		}
	}
	for(int i=1;i<=n;i++)
	   cout<<ancest[i]<<endl;
	return 0;
}


Measured memory_bytes: 7040
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    string S; cin >> S;

    int R = N;
    vector<int> dist(N+1,1e9);
    dist[N] = 0;
    for (int i = N-1; i >= 0; i--) {
        if (S[i]=='1') continue;
        while (S[R]=='1' or R-i > M) R--;
        if (i==R) {
            cout << -1 << ln;
            return 0;
        }
        dist[i] = dist[R]+1;
    }
    int cur = dist[0];
    int num = 0;
    vector<int> ans;
    rep(i,N+1) {
        if (dist[i] > cur-1) continue;
        ans.emplace_back(i-num);
        num = i;
        cur--;
    }

    for (auto i : ans) cout << i << " ";
    cout << ln;
}



Measured memory_bytes: 4316
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::cin >> n;
    long long int ans = 0;
    for(int i = 1;i <= n;i++){
        if(i % 3 != 0 && i % 5 != 0){
            ans += i;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define INF 1e9
#define MAX_V 51
using namespace std;
typedef vector<int> V;
const V zero(51,0);
struct edge{
  int to,rev;
  V cap;
  edge();
  edge(int to,V cap,int rev):to(to),cap(cap),rev(rev){};
};

bool compare (const V &a,const V &b){
  for(int i=a.size()-1;i>=0;i--)if(a[i]!=b[i])return a[i]<b[i];
  return 0;
}
V min(V &a,V &b){return compare(a,b)? a:b;}

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,V cap){
  G[from].push_back(edge(to,cap,G[to].size()));
  G[to].push_back(edge(from,cap,G[from].size()-1));  
}

void add(V &a,V &b){for(int i=0;i<(int)a.size();i++)a[i]+=b[i];}
void sub(V &a,V &b){for(int i=0;i<(int)a.size();i++)a[i]-=b[i];}

//?¢?????????????DFS??§??¢???
V dfs(int v,int t,V f){
  if(v == t)return f;
  used[v]=true;
  for(int i=0; i<G[v].size() ;i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap != zero){
      V d = dfs(e.to ,t , min(f,e.cap));
      if(d != zero){
	sub(e.cap,d);
	add(G[e.to][e.rev].cap,d);
	return d;
      }
    }
  }
  return zero;
}

//s??????t???????????§???????±???????
V max_flow(int s,int t){
  V flow=zero;
  for(;;){
    memset(used,0,sizeof(used));
    V f = dfs(s, t, V(51,1e4));
    if(f == zero)return flow;
    add(flow,f);
  }
}

int StoI(string &a,int &i){
  int res=0;
  while(isdigit(a[i])) res=res*10+a[i++]-'0';
  return res;
}

string ItoS(int a){
  string res;
  while(a) res=char(a%10+'0')+res,a/=10;
  if(res.empty()) res="0";
  return res;
}

V StoV(string s){
  if(s=="0") return zero;
  V res(51);
  for(int i=0;i<s.size();i++){
    int a = max(1,StoI(s,i));
    int L = 0;
    if(s[i]=='x')i+=1+(s[i+1]=='^'),L=max(1,StoI(s,i));
    res[L] = a;
  }
  return res;
}

string VtoS(V a){
  string res;
  for(int i=a.size()-1;i>=0;i--){
    if(a[i]==0)continue;
    if(!res.empty()) res+='+';
    if(a[i]>1||i==0) res+=ItoS(a[i]);
    if(i)res+='x';
    if(i>1) res+='^'+ItoS(i);
  }
  if(res.empty()) res="0";
  return res;
}

int main(){
  while(1){
    int n,m;
    cin>>n>>m;
    if(!n&&!m) return 0;
    for(int i=0;i<MAX_V;i++) G[i].clear();
    for(int i=0,a,b;i<m;i++){
      string c;
      cin>>a>>b>>c;
      V vc = StoV(c);
      add_edge(a-1,b-1,vc);
    }

    V ans = max_flow(0,n-1);
    cout<<VtoS(ans)<<endl;
  }
  return 0;
}

Measured memory_bytes: 3300
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
ll a[20];
int main()
{
    ll sum;
    cin>>sum;
    int k=0;
    while(sum!=0)
    {
        ll t=sum%26;
        sum/=26;
        if(t==0) {t=26;sum--;}
        a[k++]=t;
    }
    int i;
    for(i=k-1;i>=0;i--)
    {
        char c=a[i]+'a'-1;
        printf("%c",c);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 3632
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]

memo = [0]*w
ans = [[0]*w for _ in range(h)]
count = 1

for i in range(h):
    if any((s[i][j] == '#' for j in range(w))):
        num1 = i
        flag = True
        for j in range(w):
            if s[i][j] == '#':
                if flag:
                    flag = False
                    memo[j] = count
                else:
                    count += 1
                    memo[j] = count
            else:
                memo[j] = count
        break

for i in range(num1+1):
    for j in range(w):
        ans[i][j] = memo[j]

for i in range(num1+1,h):
    if '#' not in s[i]:
        for j in range(w):
            ans[i][j] = memo[j]
    else:
        count += 1
        flag = True
        for j in range(w):
            if s[i][j] == '#':
                if flag:
                    flag = False
                    memo[j] = count
                    ans[i][j] = count
                else:
                    count += 1
                    memo[j] = count
                    ans[i][j] = count
            else:
                memo[j] = count
                ans[i][j] = count

for i in range(h):
    for j in range(w):
        if j != w-1:
            print(ans[i][j],end = ' ')
        else:
            print(ans[i][j],end = '')
            print()


Measured memory_bytes: 7568
// C++ 14
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)

using namespace std;

#define N_MAX 100001

typedef struct Edge { Int v, w; }Edge;

Int N;
Int d[N_MAX];
vector<Edge> edges[N_MAX];


Int bfs(Int u) {
    loop(i,0,N) {
        d[i] = -1;
    }
    
    queue<Int> Q;
    
    Q.push(u);
    d[u] = 0;
    
    while (!Q.empty()) {
        Int parent = Q.front(); Q.pop();
        for (auto child: edges[parent]) {
            if (d[child.v] != -1) continue;
            Q.push(child.v);
            d[child.v] = d[parent] + child.w;
        }
    }
    
    Int maxIndex = 0;
    loop(i,1,N) {
      if (d[maxIndex] < d[i]) maxIndex = i;
    }
    
    return maxIndex;
}


Int diametar() {
  Int u = bfs(0);
  Int v = bfs(u);
  return d[v];
}

int main(void) {
  Int u, v, w;
  cin >> N;
  while (cin >> u >> v >> w) {
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }
  
  cout << diametar() << endl;
}



Measured memory_bytes: 9868
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int dp[200005];
int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=1;i<=n;i++){
		dp[i%k]++;
	}
	LL ans = 0;
	for(int i=0;i<=n;i++){
		if( (i+i)%k == 0){
			ans = (ans + (LL)dp[i]*dp[i]*dp[i]);
		}
	}
	printf("%lld\n", ans);
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i_len=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back
#define mp make_pair


bool isPrime(ll n)
{
    bool f = true;
    if(n == 1 || (n % 2 == 0 && n != 2)) f = false;
    else {
        for(ll i=3; i*i<=n; i+=2) {
            if(n % i == 0){
                f = false;
                break;
            }
        }
    }
    return f;
}

int main()
{
    ll X;
    cin >> X;

    for(ll i=X; ; ++i) {
        if(isPrime(i)) {
            PR(i);
            break;
        }
    }

    return 0;
}

/*



*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    string S;
    cin >> S;
    string ref = "CODEFESTIVAL2016";
    int ans;
    REP(i,S.length()){
        if(S[i] != ref[i]){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
 int n,k,x,y,s;
 scanf("%d",&n);
 scanf("%d",&k);
 scanf("%d",&x);
 scanf("%d",&y);

 if(n-k>0){
  s=k*x+(n-k)*y;
  printf("%d\n",s);}
 else{
  s=n*x;
  printf("%d\n",s);
 }

 return 0;
}


Measured memory_bytes: 128
import sys

N, M = map(int, input().split())
A = [list(map(int, sys.stdin.readline().rsplit()))[1:] for _ in range(N)]
S = [0] * M

for i in range(N):
    for a in A[i]:
        S[a - 1] += 1

res = 0
for s in S:
    if s == N:
        res += 1
print(res)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int N; 
  cin >> N;

  vector<int> A(N*3);
  REP(i, N*3) cin >> A[i];

  sort(ALL(A));

  int ans = 0;
  int cnt = N;
  for(int i = N*3-2; --cnt >= 0; i -= 2){
    ans += A[i];
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 2560
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

int main(){
    int n;
    
    long long a,b;
    while(cin >> n >> a >> b&&n!=0){
        a--;b--;
        string s;   
        rep(i,n){
            if(a%2!=b%2){
                s.push_back('R');
            }else{
                s.push_back('L');
            }
            if(a >= (1LL<<(n-i-1))){
                a -= (1LL<<(n-i-1));
            }else{
                a = (1LL<<(n-i-1))-1- a;
            }
            b/=2;
        }
        reverse(s.begin(),s.end());
        cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 200009
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;

int m,n,x,y,fac[N],inv[N];
int main(){
	scanf("%d%d%d%d",&m,&n,&x,&y);
	int i;
	fac[0]=inv[0]=inv[1]=1;
	for (i=1; i<N; i++) fac[i]=(ll)fac[i-1]*i%mod;
	for (i=2; i<N; i++) inv[i]=mod-(ll)inv[mod%i]*(mod/i)%mod;
	for (i=2; i<N; i++) inv[i]=(ll)inv[i]*inv[i-1]%mod;
	int ans=cbn(m+n-2,m-1);
	for (i=1; i<=y; i++)
		ans=(ans-cbn(i-2+m-x,m-x-1)*cbn(x-1+n-i,x-1)%mod+mod)%mod;
	printf("%d\n",ans); 
	return 0;
}


Measured memory_bytes: 1792
#include <numeric>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> ans;
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    int prevlast = -1;
    while (k >= 0) {
        sort(v.begin(), v.end(), [&](int i, int j) { return a[i] > a[j]; });
        int curlast;
        for (int i = 0; i < n; i++) {
            int j = v[i];
            if (j == prevlast) continue;
            curlast = j;
            if (a[j] == 0) { cout << -1 << endl; return 0; }
            ans.push_back(j);
            a[j]--;
            // cerr << i << ' ' << j << ' ' << a[j] << ' ' << prev << ' ' << k << endl;
        }
        prevlast = curlast;
        k--;
    }

    cout << ans.size() << endl;
    for (int x : ans) cout << x+1 << ' ';
    cout << endl;
}


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

int main() {
    int N, YEN;
    cin >> N >> YEN;

    int X = -1;
    int Y = -1;
    int Z = -1;
    for (int x = 0; x <= N; x++) {
        for (int y = 0; x + y <= N; y++) {
            int z = N - x - y;
            if (10000 * x + 5000 * y + 1000 * z == YEN) {
                X = x;
                Y = y;
                Z = z;
            }
        }
    }
    cout << X << " " << Y << " " << Z << endl;

}

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <complex>

#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define RALL(c) (c).rbegin(), (c).rend()
#define ALLA(a,n) ((a)+0), ((a)+n)

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<string> vstring;
typedef vector<double> vdouble;

template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<< ' ' ; cout << endl; }
template<class T>void pp(T v){ EACH(it,v) cout << *it << ' ' ; cout << endl;  }
template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a; }
template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a; }
inline ll to_i(const string& s){ll n;sscanf(s.c_str(),"%lld",&n);return n;}
inline string to_s(ll n){char buf[32];sprintf(buf,"%lld",n);return string(buf);}

struct __scanner__{ bool e; operator bool(){ return e; } } IN = { false };
inline __scanner__& operator>>(__scanner__& in,int &n)
{ in.e = scanf("%d",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,ll &n)
{ in.e = scanf("%lld",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,double &n)
{ in.e = scanf("%lf",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,char &n)
{ in.e = scanf(" %c",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,string &n) // BUFFER SIZE!
{ static char buf[1000000]; in.e = scanf(" %s",buf)==1; n = buf; return in; } 

int main(){
  int n;
  while (cin >> n) {
    int result = 0;
    REP(iter, n) {
      int l, r; cin >> l >> r;
      result += r - l + 1;
    }
    cout << result << endl;
  }
}


Measured memory_bytes: 256
// finish date: 2018/05/05
#include <bits/stdc++.h>


using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int H, W;
    cin >> H >> W;
    vs s(H);
    rep(i, H) cin >> s[i];
    rep(i, H) {
        rep(j, W) {
            if (s[i][j] == '.') continue;
            for (int x = -1; x <= 1; x += 2) {
                if (0 <= j + x && j + x < W && s[i][j+x] == '#') goto outer;
            }
            for (int y = -1; y <= 1; y += 2) {
                if (0 <= i + y && i + y < H && s[i+y][j] == '#') goto outer;
            }
            cout<<"No"<<endl;
            return 0;
            outer:;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 5000000000000000000;

constexpr int mod = 998244353;
struct ModInt {
    ll x;
    ModInt (ll a) : x((a % mod + mod) % mod) {}
    ModInt operator- () const {
        return ModInt(-x);
    }
    ModInt &operator+= (const ModInt &a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-= (const ModInt &a) {
        if ((x -= a.x) < 0) x += mod;
        return *this;
    }
    ModInt &operator*= (const ModInt &a) {
        (x *= a.x) %= mod;
        return *this;
    }
    ModInt operator+ (const ModInt &a) const {
        ModInt res(*this);
        return res += a;
    }
    ModInt operator- (const ModInt &a) const {
        ModInt res(*this);
        return res -= a;
    }
    ModInt operator* (const ModInt &a) const {
        ModInt res(*this);
        return res *= a;
    }
    ModInt pow(ll t) const {
        if (!t) return 1;
        ModInt a = pow(t / 2);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    ModInt inv() const {
        return pow(mod - 2);
    }
    ModInt &operator/= (const ModInt &a) {
        return (*this) *= a.inv();
    }
    ModInt operator/ (const ModInt &a) const {
        ModInt res(*this);
        return res /= a;
    }
    friend istream &operator>> (istream &is, ModInt &a) {
        is >> a.x;
        return is;
    }
    friend ostream &operator<< (ostream &os, const ModInt &a){
        os << a.x;
        return os;
    }
};

int main() {
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    
    vector<vector<ModInt>> dp(N + 1, vector<ModInt>(S + 1, ModInt{0}));
    dp[0][0] = ModInt{1};
    rep(i, N) rep(j, S + 1) {
        dp[i + 1][j] += dp[i][j] * 2;
        if (j + A[i] <= S) dp[i + 1][j + A[i]] += dp[i][j];
    }
    cout << dp[N][S] << "\n";
    return 0;
}


Measured memory_bytes: 73676
from math import gcd
K = int(input())

#dp = [[[-1] * 210 for _ in range(210)] for _ in range(210)]
ans = 0
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            size = len(set([a, b, c]))
            gd = gcd(a, gcd(b, c))
            if size == 1:
                ans += gd
            elif size == 2:
                ans += 3 * gd
            else:
                ans += 6 * gd
print(ans)


Measured memory_bytes: 68064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

	int q;
	cin >> q;
	int k;
	
	for (int i = 0; i < q; i++) {
		cin >> k;
		cout << lower_bound(A, A + n, k) - A << " " << upper_bound(A, A + n, k) - A << endl;
	}   
}


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

int main(void){
    int n;
    cin>>n;
    vector<int> a(n);
    
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    
    long long int x=0,y=0;
    for(int i=n-1;i>0;i--){
        if(a[i] == a[i-1]){
            if(x == 0){
                x=a[i];
                i--;
            }
            else{
                y=a[i];
                break;
            }
        }
    }
    cout << x*y << endl;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main{
    public static void main(String args[]){
	try{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    int n = Integer.parseInt(str);
	    double init = 100000;
	    for(int i=0;i<n;i++){
		init = init * 1.05;
		if((init / 1000) % 1 > 0){
		    init = (init/1000 - ((init / 1000) % 1) + 1)*1000;
		}
	    }
	    System.out.printf("%d\n",(int)(init));
	}
	catch(Exception e){
	    System.exit(0);
	}
    }
}

Measured memory_bytes: 16896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
ll MM = 1000000000; ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
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;}
const ll INF = 1LL << 60;
//cout << fixed << setprecision(10);

int main(){
    ll a,b,m,ans=INF; cin>>a>>b>>m;
    vector<ll>v(a),w(b);
    rep(i,a) cin>>v[i];
    rep(i,b) cin>>w[i];
ll x,y,c;
rep(i,m){
    cin>>x>>y>>c;
    chmin(ans,v[x-1]+w[y-1]-c);
}
sort(all(v));
sort(all(w));
chmin(ans,v[0]+w[0]);
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


A, B, C, D = map(int, input().split())

# B以下で割り切れる
UB_C = B // C
UB_D = B // D
UB_CD = B // lcm(C, D)

UB = B - (UB_C + UB_D - UB_CD)

# A以下で割り切れる
UA_C = A // C
UA_D = A // D
UA_CD = A // lcm(C, D)

UA = A - (UA_C + UA_D - UA_CD)

ans = UB - UA

if A % C != 0 and A % D != 0:
    ans += 1

print(ans)


Measured memory_bytes: 3064
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
c=1
for i in range(n):
    c*=b.count(a[i])
    c%=1000000007
    if b[0]==a[i]:
        b[0]+=1
    elif b[1]==a[i]:
        b[1]+=1
    else:
         b[2]+=1
print(c)

Measured memory_bytes: 13964
import math
x,n=map(int,input().split())
arr=list(map(int,input().split()))
min1,ans1=float('INF'),float('INF')
for i in range(x,x+n+1):
    if i not in arr:
        min1=abs(i-x)
        ans1=i
        break
min2,ans2=float("INF"),float("INF")
for i in reversed(range(x-n,x+1)):
    if i not in arr:
        min2=abs(i-x)
        ans2=i
        break

if min1>min2:
    print(ans2)
elif min1==min2:
    print(min([ans1,ans2]))
else:
    print(ans1)


        
    
        


Measured memory_bytes: 9204
# frozen_string_literal: true

require 'prime'

module Residue
  MODULO = 1_000_000_007
  def self.inv(x)
    extgcd(x, MODULO)[0] % MODULO
  end

  def self.pow(x, i)
    retun 1 if i == 0
    r = 1
    i %= (MODULO - 1)
    while i > 0
      r = (r * x) % MODULO if (i & 1) != 0
      x = (x * x) % MODULO
      i >>= 1
    end
    r
  end

  def self.extgcd(a, b)
    x_2 = 1
    x_1 = 0
    y_2 = 0
    y_1 = 1
    r_2 = a
    r_1 = b
    loop do
      q, r = r_2.divmod(r_1)
      x = x_2 - q * x_1
      y = y_2 - q * y_1
      break if r == 0

      x_2 = x_1
      x_1 = x
      y_2 = y_1
      y_1 = y
      r_2 = r_1
      r_1 = r
    end
    [x_1, y_1, r_1]
  end
end


primes = Prime.each(1_000_000).to_a
n = gets.to_i
an = gets.split(' ').map(&:to_i)
pn = an.map { |ai| Prime.prime_division(ai) }
lcm_div = primes.zip(Array.new(primes.size, 0)).to_h
pn.each do |hi|
  hi.each do |arr|
    k, v = arr
    lcm_div[k] = v if lcm_div[k] < v
  end
end
lcm_div.reject! { |_k, v| v == 0 }
lcm_prod=1
lcm_div.each do |k, v|
  lcm_prod=(lcm_prod * Residue.pow(k, v)) % Residue::MODULO
end
res=an.sum do |ai|
  (lcm_prod * Residue.inv(ai))
end % Residue::MODULO
p res


Measured memory_bytes: 28944
import java.util.*;
import java.math.*;
public class Main {
  
  	public static double halfpow (int a){
			double d = 0.5;
			return Math.pow(d,a);
		}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		double ans = 0;


        for (int i = 1; i < N+1; i++) {
			int cnt = 0;
            int j = i; 
			while (j < K)
			{
				j*=2;
				cnt++;
			}
  
			ans += halfpow(cnt);
		}
		ans = ans / N;
		
		System.out.println(ans);
	
	}
}
			

Measured memory_bytes: 36052
#include<cstdio>
#include<iostream>
const long long Maxn=1000000+10;
long long a[Maxn],cnt[Maxn][2];
long long n,ans;
inline long long read()
{
	long long s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int main()
{
	n=read();
	for(long long i=1;i<=n;++i)
	{
		a[i]=read();
		if(i-a[i]>=0)++cnt[i-a[i]][1];
		if(i+a[i]<=n)++cnt[i+a[i]][0];
	}
	for(long long i=1;i<=n;++i)
	{
		if(i-a[i]>=0)ans+=cnt[i-a[i]][0];
		if(i+a[i]<=n)ans+=cnt[i+a[i]][1];
	}
	printf("%lld\n",ans>>1);
	return 0;
}

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

using namespace std;

long long n;

void write(__int128 x) {
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}

__int128 min(__int128 a, __int128 b) {
	return a < b ? a : b;
}



int main() {
	cin >> n;
	if(n & 1ll) {
		puts("0");
	} else {
		long long base2 = 2ll, base5 = 5ll;
		__int128 cnt2 = 0, cnt5 = 0;
		for(; base2 <= n; base2 *= 2) {
			cnt2 += n / base2;
		}
		for(; base5 <= n; base5 *= 5) {
			cnt5 += n / 2 / base5;
		}
		write(min(cnt2, cnt5)); puts("");
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String sout = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if('a' <= c && c <= 'z') {
//                c = Character.toUpperCase(c);
                c = (char)(c - 'a' + 'A');
            } else if ('A' <= c && c <= 'Z') {
//                c = Character.toLowerCase(c);
                c = (char)(c - 'A' + 'a');
            } else {
                // nop
            }
            sout = sout + c;
        }
        System.out.println(sout);
    }
}


Measured memory_bytes: 31184
#include <stdio.h>
long long fun(long long n)
{
    return n*(n-1)/2;
}
int main()
{
    long long int n;
    int a[200001];
    long long int b[200001],c[200001],x=0;
    scanf("%lld",&n);
    for(int i=0;i<n+1;i++)
    {
        b[i]=0;
        c[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    for(int i=0;i<n+1;i++)
    {
        if(b[i]>1)
        {
            c[i]=fun(b[i]-1);
            b[i]=fun(b[i]);
            x+=b[i];
        }
        else b[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        printf("%lld\n",(x-b[a[i]]+c[a[i]]));
    }
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll mod=1e9+7;
int dp[101][100002];
vector<ll> v;
ll solve(int i,int j)
{
  if(dp[i][j]!=-1)
  return dp[i][j];
  if(i==0)
  return dp[i][j]=(j<=v[i]?1:0);
  if(j==0)
  return dp[i][j]=solve(i-1,j);
  ll ans=0;
  ans=(mod+solve(i,j-1)+solve(i-1,j)-((j-1-v[i]>=0)?solve(i-1,j-1-v[i]):0))%mod;
  return dp[i][j]=ans;
}
int main()
{
  memset(dp,-1,sizeof(dp));
  int n,k;
  cin>>n>>k;
  v.resize(n);
  for(ll& x:v)
  cin>>x;
  cout<<solve(n-1,k)<<endl;
  return 0;
}

Measured memory_bytes: 50876
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

int main(){
    std::vector<int> a(5);
    for(int i = 0; i < 5; ++i){
        std::cin >> a.at(i);
    }

    int k;
    std::cin >> k;

    bool flg = true;
    for(int i = 0; i < 5; ++i){
        for(int j = 0; j < 5; ++j){
            if(abs(a.at(i) - a.at(j)) > k){
                flg = false;
                break;
            }
        }
    }

    if(flg){
        std::cout << "Yay!" << std::endl;
    }else{
        std::cout << ":(" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 888
//2019.5.15 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
inline int read() {
    res s=0,ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline LL Read() {
    RG LL s=0;
    res ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=200+10;
namespace MAIN {
    int n,m;
    char str[N][N];
    int dp[2][N][N][N],ans;
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)scanf("%s",str[i]+1);
        res cur=0;
        for(res i=n;i;i--)
            for(res j=i;j<=n;j++)
                for(res h=m;h;h--){
                    res &DP=dp[0][i][j][h];
                    if(i==j||(str[i][h]==str[i+1][h]&&dp[0][i+1][j][h]>h)){
                        if(h!=m&&str[i][h]==str[i][h+1])DP=dp[0][i][j][h+1];
                        else DP=h+1;
                    }
                    else DP=h;
                }
        while(dp[cur][1][n][1]!=m+1){
            for(res i=n;i;i--)
                for(res j=i;j<=n;j++)
                    for(res h=m;h;h--){
                        res &DP=dp[cur^1][i][j][h],DP0=dp[cur][i][j][h];
                        DP=(DP0<=m?dp[cur][i][j][DP0]:m+1);
                        if(i!=j){
                            res l=i,r=j-1;
                            while(l<=r){
                                res mid=(l+r)>>1,F=dp[cur][i][mid][h],G=dp[cur][mid+1][j][h];
                                DP=max(DP,min(F,G));
                                if(F>G)l=mid+1;
                                else r=mid-1;
                            }
                        }
                    }
            cur^=1,ans++;
        }
        printf("%d\n",ans);
    }
}
int main() {
//    srand((unsigned)time(NULL));
//    freopen("graph.in","r",stdin);
//    freopen("graph.out","w",stdout);
    MAIN::MAIN();
    return 0;
}


Measured memory_bytes: 67456
n,k=gets.chomp.split(" ").map { |e| e.to_i  }

h = []

n.times do |i|
  h[i] = gets.chomp.to_i
end

h = h.sort

ans = 100000000000

for i in 0..n-k do
  temp = h[i+k-1] - h[i]
  ans = temp > ans ? ans : temp
end

puts ans


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

int main() {
    int N;
    cin >> N;

    vector<int> X(N);
    rep(i, N) {
        cin >> X.at(i);
    }

    int min = 0;
    rep(i, N) {
        min += (X.at(i) - 1) * (X.at(i) - 1);
    }
    int tmp;
    rep2(j, 1, 100) {
        tmp = 0;
        rep(i, N) {
           tmp += (X.at(i) - j) * (X.at(i) - j);
        }
        min = tmp < min ? tmp : min;
    }

    cout << min << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    
    public void solve(){
       Scanner sc = new Scanner(System.in);
	   int ninzu,k;
	   int ban;
	   for(int i=0;i<4;i++){
	   	ban = sc.nextInt();
		if(ban == 1){
			k = 6000;
		}else if(ban == 2){
			k = 4000;
		}else if(ban == 3){
			k = 3000;
		}else{
			k = 2000;
		}
		ninzu = sc.nextInt();
		int uriage = k*ninzu;
		System.out.println(uriage);
	   }
    }
    public static void main(String[] args){
        Main obj = new Main();
        obj.solve();
    }
}

Measured memory_bytes: 17168
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

sx, sy, gx,gy = map(int, input().split())



Y = abs(gy - sy)
X = abs(gx - sx)



output = ""
output += "U"*abs(Y)
output += "R"*abs(X)
output += "D"*abs(Y)
output += "L"*abs(X)

output += "L"

output += "U"*(abs(Y)+1)
output += "R"*(abs(X)+1)

output += "DR"

output += "D"*(abs(Y)+1)
output += "L"*(abs(X)+1)

output += "U"
print(output)

Measured memory_bytes: 38384