akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<cstdio>
#include<cstring>
#define M 10001
#define N 101
using namespace std;
int A[N][N],B[M],C[N][N],D[N][N],b[N],d[N],m,n;bool a[N][N],c[N];
bool dfs(int u)
{
	c[u]=true;
	for(int i=1;i<=n;i++)if(a[u][i]&&(!d[i]||!c[d[i]]&&dfs(d[i])))
	{
		b[d[i]=u]=i;
		return true;
	}
	return false;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1,u;j<=m;j++)scanf("%d",&u),B[u]=A[i][(u+m-1)/m],A[i][(u+m-1)/m]=u;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=A[i][j];
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)if(!b[j])dfs(j),memset(c+1,0,n); 
		for(int j=1;j<=n;j++)C[j][i]=A[j][b[j]];
		for(int j=1;j<=n;j++)if(!(A[j][b[j]]=B[A[j][b[j]]]))b[j]=d[b[j]]=a[j][b[j]]=0;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("%d%c",C[i][j],j==m?'\n':' ');
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)D[j][i]=C[i][j];
	for(int i=1;i<=m;i++)sort(D[i]+1,D[i]+n+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("%d%c",D[j][i],j==m?'\n':' ');
	return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

const int INF = 1e9;
const long long LINF = 1e18;
const double PI=3.14159265358979323846;

typedef priority_queue<int, vector<int>, greater<int>> priority_queue_asc;

int main() {
    ll N, D;
    cin >> N >> D;

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ll Xi, Yi;
        cin >> Xi >> Yi;
        if (Xi * Xi + Yi * Yi <= D * D) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3184
#include<iostream>
#include<vector>

using namespace std;

class point
{
public:
	double x,y;
	bool used;
	point()
	{
		used=false;
	}
	void input()
	{
		char c;
		cin>>x>>c>>y;
	}
};

point *getmin(vector<point> *p)
{
	int min=0;
	for(int i=0;i<p->size();i++)
	{
		if(p->at(i).x<p->at(min).x)
		{
			min=i;
		}
	}
	return &p->at(min);
}

point sub(point *a, point *b)
{
	point ans;
	ans.x=a->x-b->x;
	ans.y=a->y-b->y;
	return ans;
}

double cross(point a, point b)
{
	return a.x*b.y-a.y*b.x;
}

bool allleft(point *a, point *b, vector<point> *v)
{
	for(int i=0;i<v->size();i++)
	{
		if(&v->at(i)!=a&&&v->at(i)!=b)
		{
			if(cross(sub(b,a),sub(&v->at(i),a))<=0)return false;
		}
	}
	return true;
}

point *getnextpoint(point *p,vector<point> *v)
{
	for(int i=0;i<v->size();i++)
	{
		if(p!=&v->at(i)&&allleft(p,&v->at(i),v))
		{
			return &v->at(i);
		}
	}
}

int solve(vector<point> *p)
{
	point *ptr=getmin(p);
	while(ptr->used==false)
	{
		ptr->used=true;
		ptr=getnextpoint(ptr,p);
	}
	int n=0;
	for(int i=0;i<p->size();i++)
	{
		if(p->at(i).used==false)n++;
	}
	return n;
}

int main(void)
{
	while(1)
	{
		int n;
		cin>>n;
		if(n==0)break;
		vector<point> p(n);
		for(int i=0;i<n;i++) p[i].input();
		cout<<solve(&p)<<endl;
	}
}

Measured memory_bytes: 1236
#include<iostream>
using namespace std;
int n,x,nr;

int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x;
		while(x%2==0){
			++nr;
			x>>=1;
		}
	}
	cout<<nr<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class X> void DEBUG(X d, T e){if(DEBUG_OUT == false)return;std::cout <<d<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T > using matrix = vector< vector< T > >;

//FUNCTION  


void solve(void)
{
  int N;
  cin>>N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++)
  {
    cin>>vec[i];
  }
  sort(ALL(vec));
  int X = vec[N/2] - vec[N/2-1] ;
  cout<<X<<endl;
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


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

int main(){
  int N;
  ll K,x=0;
  cin >> N >> K;

  VLL A(N);
  rep(i,N) cin >> A[i];

  for(int d = 62; d >= 0; d--){
    ll c = 0;
    rep(i,N) c += (A[i] >> d) & 1;
    if(2 * c < N && (x | (1LL << d)) <= K) x |= 1L << d;
  }
  ll ans = 0;
  rep(i,N) ans += x ^ A[i];
  cout << ans << endl;
  return 0;
}


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

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> ans(n);
  rep(j,n) ans[a[j] - 1] = j + 1;
  rep(k,n) cout << ans[k] << " ";
}

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

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

using ll = long long;

#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 pb push_back
#define mp make_pair
#define fill(x, y) memset(x, y, sizeof(x))
#define even(x) x % 2 == 0
#define odd(x) x % 2 != 0
#define all(x) x.begin(), x.end()
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

// these functions return the position of result of Binary Search.
#define LB(s, t, x) (int) (lower_bound(s, t, x) - s)
#define UB(s, t, x) (int) (upper_bound(s, t, x) - s)

ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx8[] = { 1, -1, 0, 0, 1, 1, -1, -1 }, dy8[] = { 0, 0, -1, 1, -1, 1, -1, 1 };

template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts>
auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); }
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }
// auto dp = make_v<int>(4, h, w);
// fill_v(dp, 0);

const ll INF_LL = (1ll << 60);
const int INF_INT = (int)1e9;
const ll MOD_CONST = (ll)(1e9 + 7);

template <class T>
bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T>
bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

inline tuple<ll, ll> rotate45(tuple<ll, ll> point) { ll x = get<0>(point), y = get<1>(point); return tuple<ll, ll>(x + y, x - y); }
inline bool rangeCheck2D(int nx, int ny, int Width, int Height) { return nx >= 0 and nx < Width and ny >= 0 and ny < Height; }
void out_sequence(vector<ll> &out) { REP(i, out.size()) { cout << out[i]; if (i == out.size() - 1) cout << endl; else cout << " "; } }



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

	ll N; cin >> N;
	vector<ll> a(N); REP(i, N) cin >> a[i];
	ll ans = 0;
	REP(i, N) {
		REP(j, N) {
			if (i == j) continue;
			chmax(ans, abs(a[i] - a[j]));
		}
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <ctime>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <cmath>
#include <functional>
#include <memory.h>

// pi = atan(1)*4;

#define INTMAX 2100000000

using namespace std;

long long int dp[51][51];

int main(void)
{
	int n, a, b;
	vector <double> v;
	double t;
	long long int c[51][51] = { 0, };

	for (int i = 0; i < 51; i++)
	{
		c[i][0] = 1;
		c[i][i] = 1;
		for (int j = 1; j < i; j++)
		{
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
	cin >> n >> a >> b;

	for (int i = 0; i < n; i++)
	{
		cin >> t;
		v.push_back(t);
	}

	sort(v.rbegin(), v.rend());
	double mean = 0;

	for (int i = 0; i < a; i++)
	{
		mean += v[i];
	}
	mean /= a;

	int num = 0, pos = 0;
	for (int i = 0; i < n; i++)
	{
		if (v[i] == v[a - 1])
		{
			num++;
			if (i < a)
			{
				pos++;
			}
		}
	}

	long long int res = 0;
	if (pos == a)
	{
		for (int i = a; i <= b; i++)
		{
			res += c[num][i];
		}
	}
	else
	{
		res += c[num][pos];
	}

	printf("%.6lf \n", mean);
	cout << res << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 2010
#define Add(u, v) ({f[++l] = (Edge) {v, head[u]}; head[u] = l;})
using namespace std;
struct Edge { int to, next; } f[N * 2]; 
int head[N], l = 0, n, k, u[N], v[N], d[N], ans; 
void Dfs(int u, int fa)
{
   d[u] = d[fa] + 1;
   for (int i = head[u]; i; i = f[i].next)
      if (f[i].to != fa) Dfs(f[i].to, u);
}
int main()
{
   cin >> n >> k; ans = 1e9;  
   for (int i = 1; i < n; i++) {
      scanf("%d%d", &u[i], &v[i]);
      Add(u[i], v[i]); Add(v[i], u[i]);
   }
   if (k % 2 == 0) {
      for (int i = 1; i <= n; i++) {
	 int sum = 0; 
	 d[0] = -1; Dfs(i, 0);
	 for (int j = 1; j <= n; j++)
	    if (d[j] > k / 2) sum++;
	 ans = min(ans, sum);
      }
   }
   else {
      for (int i = 1; i < n; i++) {
	 int sum = 0; 
	 d[v[i]] = -1; Dfs(u[i], v[i]);
	 d[u[i]] = -1; Dfs(v[i], u[i]);
	 for (int j = 1; j <= n; j++)
	    if (d[j] > k / 2) sum++;
	 ans = min(ans, sum); 
      }
   }
   cout << ans << endl; 
   return 0; 
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

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

const ll MAX_N = 100000;
int vmap[MAX_N];

int main(){
	int H, W;
	cin >> H >> W;
	int i, j;
	vector<string> S;
	for (i = 0; i < H; i++){
		string s;
		cin >> s;
		S.push_back(s);
	}
	for (i = 0; i < H; i++){
		for (j = 0; j < W; j++){
			if (S[i][j] == '.'){
				int n = 0;
				for (int k = -1; k <= 1; k++){
					if (i + k < 0 || i + k >= H){
						continue;
					}
					for (int l = -1; l <= 1; l++){
						if (j + l < 0 || j + l >= W){
							continue;
						}
						if (S[i + k][j + l] == '#'){
							n++;
						}
					}
				}
				S[i][j] = '0' + n;
			}
		}
	}
	for (i = 0; i < H; i++){
		cout << S[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
char s[310];
int K,n,f[310][310][310];
int read()
{
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
int main()
{
	scanf("%s%d",s+1,&K);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		for(int k=0;k<=K;k++)
			f[i][i][k]=1;
	for(int len=1;len<n;len++)
		for(int l=1,r=len+1;r<=n;r++,l++)
			for(int k=0;k<=K;k++)
			{
				f[l][r][k]=max(f[l+1][r][k],f[l][r-1][k]);
				if(s[l]==s[r]) f[l][r][k]=max(f[l+1][r-1][k]+2,f[l][r][k]);
				else if(k) f[l][r][k]=max(f[l+1][r-1][k-1]+2,f[l][r][k]);
			}
	printf("%d",f[1][n][K]);		
    return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<int> b(n+1,100000);
  for(int i=1;i<n;i++)
    cin >> b.at(i);
  
  int k=0;
  
  for(int i=0;i<n;i++)
    k+=min(b.at(i),b.at(i+1));
  
  cout << k << endl;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CCandies solver = new CCandies();
        solver.solve(1, in, out);
        out.close();
    }

    static class CCandies {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] top = new int[n];
            int[] bottom = new int[n];
            for (int i = 0; i < n; i++)
                top[i] = in.nextInt();
            for (int i = 0; i < n; i++)
                bottom[i] = in.nextInt();

            int sumTop = top[0];
            int sumBottom = 0;
            for (int x : bottom)
                sumBottom += x;

            int answer = sumTop + sumBottom;
            for (int k = 1; k < n; k++) {
                sumTop += top[k];
                sumBottom -= bottom[k - 1];
                answer = Math.max(answer, sumTop + sumBottom);
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21588
from itertools import product


def count(C, H, W, hselect, wselect):
    cnt = 0
    for i in range(H):
        if hselect[i]:
            continue
        for j in range(W):
            if wselect[j]:
                continue
            if C[i][j] == "#":
                cnt += 1
    return cnt


def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = 0
    for hselect in product([True, False], repeat=H):
        for wselect in product([True, False], repeat=W):
            if count(C, H, W, hselect, wselect) == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 68260
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

ll m,n;
vector<ll> vec(32,0);
void emb(){
  rep(i,32){
    if(i == 0){
      vec[i] = 1;
    }else if(i == 1){
      vec[i] = m;
    }else{
      vec[i] = vec[i-1] * vec[i-1] % mod;
    }
  }
}
ll calc(){
  emb();
  ll mul = 1;
  ll cou = 1;
  while(n != 0){
    if(n & 1){
      mul *= vec[cou];
      mul %= mod;
    }
    cou++;
    n = n >> 1;
  }
  return mul;
}

int main(){
  cin >> m >> n;
  cout << calc() << endl;
}



Measured memory_bytes: 3096
#include <stdio.h>
#include <algorithm>

using namespace std;

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

  if (a % 2 == 0 || b % 2 == 0) {
    printf("No\n");
  } else {
    printf("Yes\n");
  }

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5;
char str[maxn];
int nxt[maxn], pre[maxn], sz;

int main(){
	scanf("%s", str + 1);
	int sz = strlen(str + 1);
	for(int i = 0; i <= sz + 1; i++){
		pre[i] = i - 1;
		nxt[i] = i + 1;
	}
	nxt[sz + 1] = -1;
	int head = 0, tail = sz + 1;
	for(int p = 1, q = 2; q != tail && sz > 1;){
		p = pre[q];
		if(str[p] == 'S' && str[q] == 'T'){
			p = pre[p];
			nxt[p] = nxt[q];
			pre[nxt[q]] = p;
			q = nxt[q];
			sz -= 2;
		}else q = nxt[q];
	}
	printf("%d\n", sz);
	return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll N ;
    cin >> N ;
    string S,T;
    cin >> S;
    map<pair<string,string>,ll> ml,mr;
    for(ll i = 0 ; i < 1LL << N ;i++){
        string a,b;
        rep(j,N){
            if( (i>>j) & 1){
                a.push_back(S[j]);
            }else b.push_back(S[j]);
        }
        ml[{a,b}]++;
    }
    for(int i=N;i<2*N;i++)T.push_back(S[i]);
    reverse(ALL(T));
    for(ll i = 0 ; i < 1LL << N ;i++){
        string a,b;
        rep(j,N){
            if( (i>>j) & 1){
                a.push_back(T[j]);
            }else b.push_back(T[j]);
        }
        mr[{a,b}]++;
    }
    ll ans = 0;
    for(auto x:ml){
        ans += x.second * mr[x.first];
    }
    cout << ans << endl;
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K; cin >> K;
    string S; cin >> S;
    if(S.length() <= K) cout << S << endl;
    else{
        string ans = "";
        rep(i, K) ans += S[i];
        cout << ans << "..." << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        ((a)*((b)/gcd((a),(b))))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

    vi v(n);
    for(int i=0;i<n;++i)
        cin>>v[i];

    pii tmp;

    auto chk=[&tmp](int mn,int mx,int x)
    {
        int l=iceil(mn,x),r=mx/x;

        if(l>r)
            return 0;

        tmp=makep(l*x,(r+1)*x-1);
        return 1;
    };

    int mn=2,mx=2;
    for(int i=n-1;i>=0;--i)
    {
        if(!chk(mn,mx,v[i]))
        {
            cout<<-1;
            return;
        }

        mn=tmp.F;
        mx=tmp.S;
    }

    cout<<mn<<" "<<mx;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 1024
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] R=new int[n];
		for(int i=0;i<n;i++){
			R[i]=sc.nextInt();
		}
		int maxv=R[1]-R[0];
		int minv=R[0];
		for(int j=1;j<n;j++){
			maxv=Math.max(maxv,R[j]-minv);
			minv=Math.min(minv,R[j]);
		}
		System.out.println(maxv);
	}
}


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

int n, k;

string ans, a;

string solve (string &S) {
	if(k == 1) return S;
	char L = S.back();
	int C = 0;
	while(S.back() == L) {
		S.pop_back();
		C++;
	}
	C = min(n, C*(1<<min(k-1, 13)));
	string R;
	while(C--) R.push_back(L);
	while(R.size() < n) {
		R.push_back(S.back());
		S.pop_back();
	}
	return R;
}

int main()
{
	ans.push_back('z'+1);
	cin >> n >> k >> a;
	string b = a;
	reverse(b.begin(), b.end());
	a += b;
	for(int i=0;i<=n;i++) {
		string T = a.substr(i, n);
		ans = min(ans, solve(T));
	}
	cout << ans << endl;
}


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

#define M_PI       3.14159265358979323846   // pi

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

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

using namespace std;

static const ll INF = 1e15;

const ll mod = 1000000007;


int main() {
	ll n;
	cin >> n;
	vector<vector<ll>> scores(n, vector<ll>(n));
	rep(i, n) {
		rep(j, n) {
			cin >> scores[i][j];
		}
	}
	vector<ll> dp(1LL << n, 0);
	rep(i, 1LL << n) {
		ll add = 0;
		for (ll j = 0; j < n; j++) {
			for (ll k = 0; k < j; k++) {
				if (i & (1LL << j)) {
					if (i & (1LL << k)) {
						dp[i] += scores[j][k];
					}
				}
			}
		}
	}
	for (ll i = 0; i < 1LL << n;i++) {
		ll u = dp[i];
		for (ll j = i; j > 0; j = ((j-1) & i)) {
			u = max(u, dp[j] + dp[(i ^ j)]);
		}
		dp[i] = u;
	}
	cout << dp[(1LL << n) - 1] << endl;
	return 0;
}


Measured memory_bytes: 3784
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s : chars,
    }

    println!("{}", funcs(s));
}

fn funcs(s : Vec<char>) -> i32 {
    fn infuncs(c: char) -> bool {
        c == 'A' || c == 'C' || c == 'G' || c == 'T'
    }
    let mut ans = 0;
    let mut hold = 0;
    for i in s {
        if infuncs(i) {
            hold += 1;
        } else {
            if ans < hold {
                ans = hold;
            }
            hold = 0;
        }
    }
    if ans < hold { ans = hold }

    ans
}



Measured memory_bytes: 4352
n = int(input())
a = list(map(int, input().split()))
d = [0 for _ in range(n-1)]
for i in range(n-1):
    d[i] = a[i+1] - a[i]
cnt = 1
l = r = cur = 0
while l < n-1:
    while r < n-1 and cur * d[r] >= 0:
        if cur == 0:
            cur = d[r]
        r += 1
    if r < n-1 and cur * d[r] < 0:
        cnt += 1
    r += 1
    l = r
    cur = 0
print(cnt)

Measured memory_bytes: 14252
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64

#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << " \n"[i==(int)v.size()-1]
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 500050;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll LINF = 1e17 + 1;
constexpr int INF = 1e9 + 1;
//int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };

void solve() {
	int H, W; cin >> H >> W;
	map<int, int> s;
	multiset<int>vals;
	REP(i, W)s[i] = i;
	REP(i, W) {
		vals.insert(0);
	}
	REP(i, H) {
		int l, r; cin >> l >> r;
		l--;
		auto it = s.lower_bound(l);
		int mr = -1;
		while (it != s.end() && it->first <= r) {
			mr = max(mr, it->second);
			vals.erase(vals.find(it->first - it->second));
			it = s.erase(it);
		}
		if (mr != -1 && r < W) {
			vals.insert(r - mr);
			s[r] = mr;
		}
		if (vals.empty())print(-1);
		else print(*vals.begin()+i+1);
	}
}



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q;
	//cin >> q;
	//while (q--)
	solve();

}


Measured memory_bytes: 22380
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const double EPS = 1e-10;
ll A[100000];
int p[100000];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	for (int i = 0; i + 1 < N; i++) {
		if (i % 2 == 0) {
			p[i]++;
			p[i + 1]--;
		}
		else {
			p[i]--;
			p[i + 1]++;
		}
	}
	sort(p, p + N);
	ll ans = 0;
	ll sum = 0;
	for (int i = N - 1; i >= 0; i--) {
		sum += A[i] * p[i];
	}
	ans = sum;
	sum = 0;
	memset(p, 0, sizeof(p));
	for (int i = 0; i + 1 < N; i++) {
		if (i % 2 == 0) {
			p[i]--;
			p[i + 1]++;
		}
		else {
			p[i]++;
			p[i + 1]--;
		}
	}
	sort(p, p + N);
	for (int i = N - 1; i >= 0; i--) {
		sum += A[i] * p[i];
	}
	ans = max(ans, sum);
	cout << ans << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<double> value(N);
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    double v = a;
    value.at(i) = v;
  }
  sort(value.begin(), value.end());
  double ans = (value.at(0) + value.at(1)) / 2;
  for(int i = 2; i < N; i++) {
    ans = (ans + value.at(i)) / 2;
  }
  cout << fixed << setprecision(6) << ans << endl;
}

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

using namespace std;

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

  char b;
  cin >> b;
  if (b == 'T') {
    cout << "A" << '\n';
  }

  if (b == 'A') {
    cout << "T" << '\n';
  }

  if (b == 'C') {
    cout << "G" << '\n';
  }

  if (b == 'G') {
    cout << "C" << '\n';
  }
}


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


int main() {
  long long N;
  cin >> N;
  int result = 11;
  for (long long a=1; a*a<=N; ++a) {
    if (N % a == 0) {
      long long b = N / a;
      long long c = max(a, b);
      for (int i=1; i<=11; ++i) {
        long long ans = c / pow(10, i);
        if (ans == 0) {
          int digit = i;
          result = min(result, digit);
          break;
        }
      }
    }
  }
  cout << result << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;

typedef unsigned long long ull;
const int N_MAX = 1e6;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
    string O, E;
    cin >> O >> E;
    int i=0;
    char res[200];
    REP(i, O.size()){
        res[i*2] = O[i];
    }
    REP(i, E.size()){
        res[i*2+1] = E[i];
    }
    for (int i=0;i<O.size()+E.size();i++){
        cout << res[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int N,A,B,memo,i,j;
	int result = 0;
	scanf("%d%d%d", &N, &A, &B);

	for (i = 1; i <= N; i++) {
		j = i;
		memo = j % 10; j = (j - (j % 10)) / 10;
	
		memo = memo+(j % 10); j = (j - (j % 10)) / 10;
	
		memo = memo + (j % 10); j = (j - (j % 10)) / 10;
		
		memo = memo + (j % 10); j = (j - (j % 10)) / 10;
		
		memo = memo + (j % 10); j = (j - (j % 10)) / 10;

		if (memo >= A && memo <= B) {
			result = result + i;
		}
	}
	printf("%d", result);
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long llong;

#define MAX 2001
const llong mod = 1000000000 + 7;

int N, X, Y;

int main()
{
  int A[MAX];
  for (int i = 0; i < MAX; i++)
  {
    A[i] = 0;
  }

  scanf("%d%d%d", &N, &X, &Y);

  for (int i = 1; i < N; i++)
  {
    int distance;
    for (int j = i + 1; j <= N; j++)
    {
      int xi = abs(X - i);
      int yj = abs(Y - j);
      distance = min(j - i, xi + yj + 1);
      A[distance]++;
    }
  }

  for (int i = 1; i < N; i++)
  {
    printf("%d\n", A[i]);
  }

  return 0;
}

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

ll a,b,c,n,m;
ll ans=100000000000;

string s;

int main() {
	cin.tie(0);
  ios::sync_with_stdio(false);
  
  cin>>n;
  if(n % 1000 == 0)
    cout<<"0";
  else
    cout<<(n/1000+1)*1000-n;

  return 0;
}



Measured memory_bytes: 3648
#include <cstdio>
#include <iostream>

using namespace std;

int gcd( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd

int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm

int main(){

  int a,b;
  
  
  while(cin >> a >> b){
    
    printf("%d %d\n",gcd(a,b),lcm(a,b));
    
  }
  
  return 0;
  
}
    


Measured memory_bytes: 1148
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    X = i_input()

    Y = X//100
    L = []
    a = [0,1,2,3,4,5]
 
    for i in range(1,min(20,Y)+1):
        c = list(itertools.combinations_with_replacement(a, i))
        for i in c:
            L.append(sum(i))
    Z = X%100
 
    if Z in L:
        print(1)
    else:
        print(0)


  
if __name__=="__main__":
    main()


Measured memory_bytes: 122352
#include <stdio.h>
 
int main(void)
{
    int q1, b, c1, c2, q2;
    int c1_n, c2_n;
	
	while (scanf("%d", &q1), q1){
		
		scanf("%d %d %d %d", &b, &c1, &c2, &q2);
		
		c1_n = c2_n = 0;
		
		while (b - c1 >= 0 && c1_n < q2){
			b -= c1;
			c1_n++;
		}
		while (b - c2 >= 0){
			b -= c2;
			c2_n++;
		}
		
		while (1){
			if (c1_n == 0){
				printf("NA\n");
				break;
			}
			else if (c1_n + c2_n >= q1){
				printf("%d %d\n", c1_n, c2_n);
				break;
			}
			else if (c1_n != 0){
				c1_n--;
				b += c1;
				c2_n += b / c2;
				b -= c2 * (b / c2);
			}
		}
	}
	
	return (0);
}
			

Measured memory_bytes: 612
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

	public void Proc()
	{
        int nodeCount = int.Parse(Reader.ReadLine());
        this.NodeList = new TreeNode[nodeCount];

        Dictionary<int, Dictionary<int, bool>> path = new Dictionary<int, Dictionary<int, bool>>();

        for (int i = 0; i < nodeCount; i++) {
            NodeList[i] = new TreeNode(i);
        }
        for (int i = 0; i < nodeCount - 1; i++) {
            int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)-1).ToArray();
            inpt.ToList().ForEach(a=>{
                if(!path.ContainsKey(a)) {
                    path.Add(a, new Dictionary<int, bool>());
                }
            });
            path[inpt[0]].Add(inpt[1], true);
            path[inpt[1]].Add(inpt[0], true);
        }
		Queue<int> que = new Queue<int>();
        path[0].ToList().ForEach(a =>
        {
            NodeList[0].AddItem(NodeList[a.Key]);
            que.Enqueue(a.Key);
        });
        while(que.Count()>0) {
            int current = que.Dequeue();
            path[current].ToList().ForEach(a =>
            {
                if(a.Key != NodeList[current].Parent.Id) {
                    NodeList[current].AddItem(NodeList[a.Key]);
                    que.Enqueue(a.Key);
                }
            });
        }
        int feneck = 0;
        int sunuke = (NodeList.Last().Depth - 1) / 2;
        TreeNode snukeRoot = NodeList.Last();
        for (int i = 0; i < sunuke; i++ ) {
            snukeRoot = snukeRoot.Parent;
        }
        que.Enqueue(snukeRoot.Id);
        sunuke = 0;
        while(que.Count() > 0) {
            int current = que.Dequeue();
            sunuke += NodeList[current].Items.Count;
            NodeList[current].Items.ForEach(a => que.Enqueue(a.Id));
        }
        feneck = nodeCount - 2 - sunuke;
        string ans = "Snuke";
        if (feneck>sunuke) {
            ans = "Fennec";
        }
        Console.WriteLine(ans);
    }

    private TreeNode[] NodeList;

    private class TreeNode
    {
        public int Id;

        public int Depth = 0;
        public TreeNode Parent;
        public List<TreeNode> Items = new List<TreeNode>();
        public TreeNode(int id)
        {
            this.Id = id;
        }
        public void AddItem(TreeNode child)
        {
            this.Items.Add(child);
            child.Parent = this;
            child.Depth = this.Depth + 1;
        }

    }


    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"

5
1 5
5 3
3 2
4 1

";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


Measured memory_bytes: 58132
#include <iostream>
#include <climits>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
	int n, a, b;
	cin >> n >> a >> b;
    string s;
    cin >> s;
    int ds = 0;
    int is = 0;
    for( int i = 0; i < n; i++ ){
        if( s[i] == 'c' ){
            cout << "No" << endl;
        } else if( s[i] == 'a' ){
            if( ds + is < a + b ){
                cout << "Yes" << endl;
                ds++;
            } else {
                cout << "No" << endl;
            }
        } else if( s[i] == 'b' ){
            if( ds + is < a + b && is < b ){
                cout << "Yes" << endl;
                is++;
            } else {
                cout << "No" << endl;
            }
        }
    }
}


Measured memory_bytes: 896
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] tmpArray = br.readLine().split(" ");

		//0 origin
		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);

		int matrix[][] = new int[n][n];
		for(int i = 0; i < n; i++){
			Arrays.fill(matrix[i], INF);
		}

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]);
			int to = Integer.parseInt(tmpArray[1]);
			int cost = Integer.parseInt(tmpArray[2]);

			matrix[from][to] = cost;
		}

		solve(matrix);
	}

//	static final int INF = 10_000_001;

	static void solve(int matrix[][]){
		//xからそれぞれのfarmへの帰り道の最短距離
		long[][] dist = warshallFloyd(matrix);

		int n = dist.length;
		for(int i = 0; i < n; i++){
			if(dist[i][i] < 0){
				System.out.println("NEGATIVE CYCLE");
				return;
			}
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(j != 0){
					System.out.print(" ");
				}
				if(dist[i][j] == INF){
					System.out.print("INF");
				}
				else {
					System.out.print(dist[i][j]);
				}
			}
			System.out.println();
		}

	}

	static final int INF = Integer.MAX_VALUE;


	static long[][] warshallFloyd(int[][] matrix){
		int n = matrix.length;

		long[][] dist = new long[n][n];

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j){
					dist[i][j] = 0;
				}
				else {
					dist[i][j] = matrix[i][j];
				}
			}
		}

		for(int k = 0; k < n; k++){
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					if(dist[i][k] == INF || dist[k][j] == INF){
						continue;
					}
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
//					System.out.println("test "+dist[i][j]);
				}
			}
		}

		return dist;
	}
}



Measured memory_bytes: 39028
# coding: utf-8
# Your code here!
N=int(input())

P=list(map(float,input().split()))

dp=[0]*(N+1)
dp[0]=1

for p in P:
    temp=[0]*(N+1)
    for i in range(N):
        temp[i+1]+=dp[i]*p
        temp[i]+=dp[i]*(1-p)
    temp[N]+=dp[N]
    dp=temp[:]

print(sum(dp[N//2+1:]))



Measured memory_bytes: 74740
#include <iostream>
#include <string>
using namespace std;
int a[6];
string s;
void C(int i, int j, int k, int l) {
	int t; t = a[i]; a[i] = a[j]; a[j] = a[k]; a[k] = a[l]; a[l] = t;
}
int main() {
	for (int i = 0; i<6; i++)cin >> a[i];
	cin >> s;
	for (int i = 0; i<s.size(); i++) {
		if (s[i] == 'E')for (int j = 0; j<3; j++)C(0, 2, 5, 3);
		if (s[i] == 'W')C(0, 2, 5, 3);
		if (s[i] == 'S')for (int j = 0; j<3; j++)C(0, 1, 5, 4);
		if (s[i] == 'N')C(0, 1, 5, 4);
	}
	cout << a[0] << endl;
}


Measured memory_bytes: 3172
#include<stdio.h>
#include<string.h>
int main(){
	char str[1002];
	char *_str;
	int i,j,n;
	for(;fgets(str,1000,stdin)!=NULL;){
		n=strlen(str);
		for(i=0;i<n;){
			if(strncmp(str,"apple",5)==0){
				printf("peach");
				n-=5;
				_str=&str[i+5];
				strcpy(str,_str);
			}
			else if(strncmp(str,"peach",5)==0){
				printf("apple");
				n-=5;
				_str=&str[i+5];
				strcpy(str,_str);
			}
			else{
				printf("%c",str[i]);
				n--;
				_str=&str[i+1];
				strcpy(str,_str);
			}
		}
	}
	exit(0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll p=998244353ll;
const int N=200005;
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}

int main(){
	int n,a;
	scanf("%d%d",&n,&a);
	printf("%d",(n-1)/(a<<1|1)+1);
	return 0;
}

Measured memory_bytes: 256
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if j > cost[k]:
                ans += 1

    print(ans//2)


if __name__ == '__main__':
    main()


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

int main() {
    int a, b;
    cin >> a >> b;
    int ans = a + b;
    if(ans > 24){
        ans = ans % 24;
    }
    if (ans == 24) {
        cout << "0" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    vector<ll> a(3*N);
    rep (i, 3*N) {
        cin >> a[i];
    }

    sort(a.rbegin(), a.rend());

    ll ans = 0;
    rep (i, N) {
        ans += a[1+2*i];
    }    

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

Measured memory_bytes: 2560
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
	sc.Split(bufio.ScanWords)

	a, b, c := getInt(), getInt(), getInt()

	out(min(a+b, min(a+c, b+c)))
}


Measured memory_bytes: 640
def train_map(LR,N):
    train = [[0 for _ in range(N+1)] for _ in range(N+1)]
    #train[i][j]:ちょうど区間iからjを走る電車の本数（後に累積和に）
    for l,r in LR:
        train[l][r] += 1

    #累積和
    for i in range(N+1):
        for j in range(1,N+1):
            train[i][j] += train[i][j-1]
    for j in range(N+1):
        for i in reversed(range(1,N+1)):
            train[i-1][j] += train[i][j]

    return train

def main():
    N,M,Q = list(map(int,input().split()))
    LR = [list(map(int,input().split())) for _ in range(M)]
    pq = [list(map(int,input().split())) for _ in range(Q)]

    train = train_map(LR,N)

    for p,q in pq:
        print(train[p][q])

if __name__ == "__main__":
    main()


Measured memory_bytes: 73336
N = int(input())
max_int = 3500
for n in range(1,max_int+1):
  for w in range(1,max_int+1):
    a1 = N*n*w
    a2 = 4*n*w-w*N-N*n
    if a2<=0:continue
    if a1%a2==0 and a1//a2<=max_int:
      print(N*n*w//(4*n*w-w*N-N*n), n, w)
      exit()

Measured memory_bytes: 40668