akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(int i=1,i##_len=(n); i<=i##_len; ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define srep(i,s,t) for(int i=(s);i<(t);++i)
#define rng(obj) (obj).begin(), (obj).end()
#define maxs(x,y) (x=max((x),(y)))
#define mins(x,y) (x=min((x),(y)))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x=max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T>>
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vp = vector<P>;
template <class T> inline istream& operator>>(istream&i,v(T)&v)
{ rep(j,sz(v))i>>v[j];return i;}
template <class T> string join(const v(T)&v)
{ stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template <class T> inline ostream& operator<<(ostream&o,const v(T)&v)
{ if(sz(v))o<<join(v); return o;}
template <class T1,class T2> inline istream& operator>>(istream&i ,pair<T1,T2>&v)
{ return i>>v.fi>>v.se;}
template <class T1,class T2> inline ostream& operator<<(ostream&o ,pair<T1,T2>&v)
{ return o<<v.fi<<","<<v.se;}
template <class T> inline ll suma(const v(T)& a) 
{ ll res(0); for(auto&& x:a) res += x; return res;}
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double eps = 1e-10;
#define dame {puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;
#define fileio ifstream fio; if(argc>=2){fio.open(argv[1]); std::cin.rdbuf(fio.rdbuf());}
#define fastio ios_base::sync_with_stdio(false);
#define MOD 1000000007
//----------------------------------------------------------------
template <class T>
map< T, int > prime_factor(T n) {
    map< T, int > ret;
    for(T i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}

void Main(){
  ll n;
  cin>>n;
  ll ans[2]; ans[0]=0;ans[1]=0;
  vl a(n);
  cin>>a;
  rep(k,2){
    ll sum = 0;
    bool pm = true, next = false;
    if(k){pm = false; next = true;}
    rep(i,n){
      sum+=a[i];
      if(pm){
        if(sum< 1){ans[k]+=1-sum; sum= 1;}
      }else{
        if(sum>-1){ans[k]+=sum+1; sum=-1;}
      }
      swap(pm,next);
    }  
  }
  cout<<min(ans[0],ans[1])<<endl;;
} int main(int argc,char* argv[]){ 
    fastio; fileio; Main();}

Measured memory_bytes: 1024
#include <stdio.h>

int main() {
    int num = 0;
    scanf("%d\n", &num);
    int v[num];
    int c[num];
    int dis[num];
    for (int i=0; i<num; i++) {
        scanf("%d", v+i);
    }
    for (int i=0; i<num; i++) {
        scanf("%d", c+i);
        dis[i] = v[i] - c[i];
    }
    int sum = 0;
    for (int i=0; i<num; i++) {
        if(dis[i] > 0) sum += dis[i];
    }
    printf("%d\n", sum);
    return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int q;
    cin >> q;
    vl a(q), b(q);
    for (int i = 0; i < q; ++i) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < q; ++i) {
        if (a[i] > b[i])
            swap(a[i], b[i]);
        if (a[i] == b[i] || abs(a[i] - b[i]) == 1) {
            cout << 2 * a[i] - 2 << "\n";
            continue;
        }
        ll c = 0;
        ll d = ll(sqrt(double(a[i]) * double(b[i])));
        for (ll j = max(0LL, d - 10); j < d + 10; ++j) {
            if (j * j < a[i] * b[i])
                c = j;
            else
                break;
        }
        if (c * c >= a[i] * b[i])
            c--;
        if (c * (c + 1) >= a[i] * b[i])
            cout << 2 * c - 2 << "\n";
        else
            cout << 2 * c - 1 << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		String[] str = s.split("\\s+");
		int ball = Integer.parseInt(str[0]);
		int color = Integer.parseInt(str[1]);
		System.out.print((int)Math.pow(color - 1,ball - 1) * color);
	}
}

Measured memory_bytes: 8148
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  ll q;
  cin >> q;
  ll n = 100000;
  vector<ll> primes;

  vector<bool> isPrime(static_cast<unsigned long>(n + 1), true);
  isPrime.at(0) = isPrime.at(1) = false;

  for (int i = 2; i <= n; ++i) {
    if (isPrime.at(i)) {
      primes.push_back(i);
      for (int j = 2 * i; j <= n; j += i) {
        isPrime.at(j) = false;
      }
    }
  }

  vector<ll> like2017(n + 1, 0);
  for (const auto &p : primes) {
    auto itr2 = find(all(primes), (p + 1) / 2);
    size_t dis2 = static_cast<size_t>(distance(primes.begin(), itr2));
    if (dis2 != primes.size()) like2017.at(p) = 1;
  }

  vector<ll> sum_like2017(n + 1, 0);

  for (int i = 1; i < n - 1; ++i) {
    sum_like2017.at(i + 1) = sum_like2017.at(i) + like2017.at(i + 1);
  }

  rep(i, q) {
    ll l, r;
    cin >> l >> r;
    --l;
    cout << sum_like2017.at(r) - sum_like2017.at(l) << endl;
  }

  return 0;
}

Measured memory_bytes: 2432
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 100000000000000000LL
using namespace std;

int main()
{
	int n, m;
	int a, b;
	scanf("%d %d", &n, &m);
	vector<int> v[100000];
	for(int i=0; i<m; i++){
		scanf("%d %d", &a, &b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int c=0;
	vector<int> conn[100000];
	int d[100000], e[100000]={};
	fill(d, d+n, -1);
	set<int> st;
	for(int i=0; i<n; i++){
		st.insert(i);
	}
	vector<int> w;
	while(!st.empty()){
		auto begin=st.begin();
		w.push_back(*begin);
		conn[c].push_back(*begin);
		d[*begin]=0;
        if(v[*begin].empty()) e[c]=2;
		st.erase(begin);
		while(!w.empty()){
			int x=w.back();
			w.pop_back();
			for(int i=0; i<v[x].size(); i++){
				if(d[v[x][i]]==-1){
					d[v[x][i]]=(d[x]+1)%2;
				}else if(d[v[x][i]]==d[x]){
					e[c]=1;
				}
				if(st.find(v[x][i])==st.end()) continue;
				w.push_back(v[x][i]);
				conn[c].push_back(v[x][i]);
				st.erase(v[x][i]);
			}
		}
		c++;
	}
	long long int cn2=0, cn0=0, cn1=0, ans=0;
	for(int i=0; i<c; i++){
		if(e[i]==2){
			cn2++;
		}else if(e[i]==1){
			cn1++;
		}else{
			cn0++;
		}
	}
	for(int i=0; i<c; i++){
		if(e[i]==2){
          ans=ans+n;
		}else if(e[i]==1){
		  ans=ans+cn2*conn[i].size()+cn0+cn1;
		}else{
          ans=ans+cn2*conn[i].size()+2*cn0+cn1;
		}
	}
	long long int N=(long long int)n;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 15484
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)



char m_cake[650][650];
ll ans[650][650];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> cpos;
vector<pair<ll,ll>> cp;
int main(){
  ll H,W,K;
  cin>>H>>W>>K;


  for(ll i=0;i<H;i++){
    for(ll j=0;j<W;j++){
      cin>>m_cake[i][j];
      if(m_cake[i][j]=='#'){
        cpos.push(make_pair(i,j));
        cp.emplace_back(make_pair(i,j));
      }
    }
  }

vector<ll> kaku[650];
  for(ll i=0;i<H;i++){
    if(cpos.empty())
    break;
    if(cpos.top().first==i){
      kaku[i].push_back(cpos.top().second);
      cpos.pop();
      i--;
    }
  }


ll num=1;
vector<ll> pre;
ll uu =-1;
vector<ll> fas;
for(ll i=0;i<H;i++){
ll satat=0;
ll ind=0;
ll pres = pre.size();
if(kaku[i].size()==0){
  kaku[i] = pre;
}
else if(kaku[i].size()==1){
  num+=pre.size();
  if(uu==-1){
    fas=kaku[i];
    uu+=100;
  }
}
else if(kaku[i].size()>=2){
num+=pres;
satat=1;
ind=0;
if(uu==-1){
    fas=kaku[i];
    uu+=1000;
  }
}
    for(ll j=0;j<W;j++){
      if(kaku[i].size()<=1){
      //cout<<num<<" ";
      ans[i][j]=num;
      }
      else{
        if(kaku[i].size()>(ind+1)&&kaku[i][ind]<j){
          ind++;
        }
        //cout<<ind+num<<" ";
         ans[i][j]=num+ind;
      }
    }
    //cout<<endl;
    pre = kaku[i];
  }



pre = fas;
num=1;
  for(ll i=0;i<cp[0].first;i++){
    ll satat=0;
ll ind=0;
ll pres = pre.size();
if(kaku[i].size()==0){
  kaku[i] = pre;
}
    for(ll j=0;j<W;j++){
      if(kaku[i].size()<=1){
      //cout<<num<<" ";
      ans[i][j]=num;
      }
      else{
        if(kaku[i].size()>(ind+1)&&kaku[i][ind]<j){
          ind++;
        }
        //cout<<ind+num<<" ";
         ans[i][j]=num+ind;
      }
    }
    //cout<<endl;
    pre = kaku[i];
  }

  

  for(ll i=0;i<H;i++){
    for(ll j=0;j<W;j++){
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }

}

/*
  for(ll i=0;i<H;i++){

ll satat=0;
ll ind=0;
if(kaku[i].size()==0){
  
}
else if(kaku[i].size()==1){
  num++;
}
else if(kaku[i].size()>=2){
num++;
 now = kaku[i];
satat=1;
ind=0;
}



    for(ll j=0;j<W;j++){
      if(satat==0)
      cout<<num<<" ";
      else{
        if(kaku[i].size()<(ind+1)&&kaku[i][ind]>j){
          ind++;
        }
        cout<<ind+num<<" ";
      }

    }
    cout<<endl;
  }







}


  
  /*

  ll num=1;
  pair<ll,ll> P = cpos.top();
  cpos.pop();

vector<ll> ddd;
while(!(cpos.empty())){
  ll ndef = cpos.top().first - P.first;
    ddd.push_back(ndef);
    P = cpos.top();
    cpos.pop();
  }


  reverse(ALL(ddd));
*/

Measured memory_bytes: 6500
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

class UnionFind {
private:
	class Node {
	public:
		int parent;

		Node(int parent) {
			this->parent = parent;
		}
	};

	int root(int x) {
		int base = x;
		while (x != node[x].parent) {
			x = node[x].parent;
		}
		node[base].parent = x;
		return x;
	}

	vector<Node> node;
public:
	UnionFind(int size) {
		for (int i = 0; i < size; i++) {
			node.push_back(Node(i));
		}
	}

	void unite(int x, int y) {
		node[root(x)].parent = root(y);
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}
};

class Edge {
public:
	int s;
	int t;
	int w;
	Edge(int s, int t, int w) {
		this->s = s;
		this->t = t;
		this->w = w;
	}

	bool operator<(const Edge &a) const {
		return w > a.w;
	}
};

signed main() {
	int V, E;
	cin >> V >> E;

	priority_queue<Edge> q;
	rep(i, E) {
		int s, t, w;
		cin >> s >> t >> w;
		q.push(Edge(s, t, w));
	}

	auto uf = UnionFind(V);

	int ret = 0;
	while (!q.empty()) {
		Edge now = q.top();
		q.pop();

		if (!uf.same(now.s, now.t)) {
			uf.unite(now.s, now.t);
			ret += now.w;
		}
	}

	cout << ret << endl;

    return 0;
}

Measured memory_bytes: 5884
s = []
S = input()

if len(S) == 1:
    print('0')
    exit()

sum = 0
for i in range(len(S)):
    s.append(S[i])

for i in range(len(S)-1):
    if s[i] == '1' and s[i+1] == '1':
        s[i+1]='0'
        sum += 1
    elif s[i] == '0' and s[i+1] == '0':
        s[i+1]='1'
        sum += 1

print(sum)

Measured memory_bytes: 3956
using System;
using System.Linq;
using System.Collections.Generic;

namespace Hoge
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x));
            var count = input.ElementAt(0);
            var result = Enumerable.Range(1, count)
                .Select(x => Console.ReadLine())
                .OrderBy(x => x)
                .Aggregate((res, cur) => res + cur);

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 14176
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cstdlib>
#define f first
#define s second
using namespace std;
typedef pair <string,int> P;
map <string,P> mp;

string find(string  x){
  if(mp[x].f!= x) mp[x] = mp[find(mp[x].f)];
  return mp[x].f;
}

bool unite(string x,string y){
  bool flg=0;
  mp[x]=mp[find(x)],mp[y]=mp[find(y)];
  if(mp[x].s != mp[y].s) flg =1;
  if(mp[x].s<mp[y].s) swap(mp[x],mp[y]);
  mp[x] = mp[y];
  return flg;
}

int main() {
  int n,m,a;
  cin >> n;
  string str;
  for(int i=0;i<n;i++) {
    cin >> str >> a;
    mp[str].f = str;
    mp[str].s = a;
  } 
  cin >> m;
  string in[2][1001];
  for(int i=0;i<m;i++) cin >> in[0][i] >> in[1][i],unite(in[0][i],in[1][i]);
  
  for(int i=0;i<m;i++){
    bool flg = 0;
    if(unite(in[0][i],in[1][i])) flg=1;
    if(flg) i = -1;
  }
  int ans = 0;
  map<string,P> :: iterator it;
  for(it=mp.begin();it!=mp.end();it++) ans += mp[find(it->f)].s;
   cout << ans <<endl;
  return 0;
}

Measured memory_bytes: 1892
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define mod (1e9 + 7)
#define pb push_back
#define ll long long int
using namespace std;
typedef pair<int,int> pii;

int main(){
  int n;

  cin>>n;

  double a,s;
  s=0;
  for(int i=0;i<n;i++){
    cin>>a;
    s+=1.0/a;
  }
  cout<<1.0/s<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
bool overlap(int a, int b, int c, int d){
  if ( d <= a ) return false;
  if ( b <= c ) return false;
  return true;
}
 
int main(){
  int a, b, s, f, n;
  cin >> a >> b >> n;
  for ( int i = 0; i < n; i++ ){
    cin >> s >> f;
    if ( overlap(a, b, s, f) ){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
  return 0;
}


Measured memory_bytes: 3104
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

S = s()
seen = set()

for c in S:
    if c in seen:
        print('no')
        import sys
        sys.exit()
    seen.add(c)

print('yes')


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

const int MAX = 100007*2;

int main(){
	int N, C, ans = 0;
	cin >> N >> C;
	int cst[C][MAX] = {0};
	int a[MAX] = {0};
	for(int i = 0; i < N; i++){
		int s, t, c;
		cin >> s >> t >> c;
		for(int j = s*2-1; j < t*2; j++)
			cst[c-1][j] = 1;
	}
	for(int i = 0; i < C; i++){
		for(int j = 0; j < MAX; j++){
			if(cst[i][j])
				a[j]++;
		}
	}
	for(int i = 0; i < MAX; i++)
		ans = max(ans,a[i]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 24448
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;


typedef long long ll;
const int MAX_V = 210;
const int INT_INF = 1<<30;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
struct edge {
	int cap, cost;
};
int V;

edge G[MAX_V][MAX_V];
int h[MAX_V], dist[MAX_V];
int prevv[MAX_V];
bool used[MAX_V];
void add_edge(int from, int to, int cap, int cost) {
	G[from][to] = (edge){1, cost};
	G[to][from] = (edge){0, -cost};
}

int bit_matching_cost(int l, int r) {
	int res = 0;
	fill_n(h, V, 0);
	while (true) {
		fill_n(dist, V, INT_INF);
		dist[l+r] = 0;

        fill_n(used, V, false);
        while (true) {
            int v = -1;
            for (int i = 0; i < V; i++) {
                if (!used[i] && (v == -1 || dist[i] < dist[v])){
                    v = i;
                }
            }
            if (v == -1) break;
            used[v] = true;

			for (int i = 0; i < V; i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && dist[i] > dist[v] + e.cost + h[v] - h[i]) {
					dist[i] = dist[v] + e.cost + h[v] - h[i];
					prevv[i] = v;
				}
			}
        }
		if (dist[l+r+1] == INT_INF) {
			break;
		}
		for (int v = 0; v < V; v++) {
			h[v] += dist[v];
		}
		res += h[l+r+1];
		for (int v = l+r+1; v != l+r; v = prevv[v]) {
			edge &e = G[prevv[v]][v];
			e.cap -= 1;
			G[v][prevv[v]].cap += 1;
		}
	}
	return res;
}
int cost[MAX_V][MAX_V];


const int MAX_N = 105;
int N;
int W[MAX_N][MAX_N], E[MAX_N][MAX_N];
bool F[MAX_N][MAX_N], F2[MAX_N][MAX_N];

int main(int argc, char *argv[]) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(W[i][j]));
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(E[i][j]));
		}
	}
	int min_f = 0, f = 0;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			F[i][j] = (s[j] == 'o');
			if (F[i][j]) {
				min_f = min(min_f, -E[i][j]);
				f += E[i][j];
			}
		}
	}
	min_f *= -1;
	V = (N+1)*2;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				add_edge(i, N+j, 1, -E[i][j]+min_f);
			} else {
				add_edge(i, N+j, 1, W[i][j]+min_f);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		add_edge(N*2, i, 1, 0);
	}
	for (int i = 0; i < N; i++) {
		add_edge(N+i, N*2+1, 1, 0);
	}
	f += bit_matching_cost(N, N);
	f -= min_f*N;
	int c = 0;
	vector<T> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == G[i][N+j].cap) {
				c++;
				q.push_back(T(i, j, F[i][j]));
			}
		}
	}
	printf("%d\n%d\n", f, c);
	for (T t: q) {
		printf("%d %d %s\n", get<0>(t)+1, get<1>(t)+1, get<2>(t) ? "erase" : "write");
	} 
    return 0;
}

Measured memory_bytes: 1768
using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

class Program
{
	//2^0 ~ 2^n-1までの各数字をmodで割ったときの余りを配列で返す
	//mod = 0のとき、全要素が0の配列を返す
	static int[] Rem(int n, int mod){
		int[] res = new int[n];

		if(mod != 0){
			int tempo = 1%mod;
			for(int i=0; i<n; i++){
				res[i] = tempo;
				//2^i+1を割った余りを計算
				tempo = (tempo*2) % mod;
			}
		}

		return res;
	}

	//文字cの出現数を高速でカウント
	static int CountChar(string s, char c) {
    return s.Length - s.Replace(c.ToString(), "").Length;
  }

	//popcount
	static int PopCount(int n){
		int res = n;
		int tempo = n/2;
		int div = 2;
		while(tempo > 0){
			res -= tempo;
			div *= 2;
			tempo = n / div;
		}

		return res;
	}

	//問題中のf(x)を再現
	static int func(int n){
		int cnt = 0;
		int tempo = n;
		while(tempo > 0){
			tempo %= PopCount(tempo);
			cnt ++;
		}

		return cnt;
	}

	//Main
	static void Main(string[] args)
	{
		//読み込む
		string S = Console.ReadLine();
		int N = int.Parse(S);
		string X = Console.ReadLine();

		//2^iをcnt+1, cnt-1それぞれで割った余りを計算しておく（0 <= i < N）
		int cnt = CountChar(X, '1');
		int minus = cnt - 1;
		int plus = cnt + 1;

		int[] remMinus = Rem(N, minus);
		int[] remPlus = Rem(N, plus);

		//Xをminus, plusそれぞれで割った余りを計算しておく
		int sumMinus= 0;
		int sumPlus = 0;
		for(int i=0; i<N; i++){
			if(X[i] == '1'){
				sumMinus += remMinus[N-i-1];
				if(minus > 0){
					sumMinus %= minus;
				}
				sumPlus += remPlus[N-i-1];
				if(plus > 0){
					sumPlus %= plus;
				}
			}
		}

		//出力準備（AutoFlushを切る）
		var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);

		//ループ処理
		for(int i=0; i<N; i++){
			//答え
			int ans = 0;

			//一回処理を行った後の値
			int res = 0;

			//popcountが増える場合（plusになる場合）
			if(X[i] == '0'){
				//2^(N-i-1)の部分の余りが増える
				res = sumPlus;
				res += remPlus[N-i-1];
				res %= plus;

				//一度処理を行ったことを反映
				ans ++;
			}
			//popcountが減る場合（minusになる場合）
			else if(minus > 0){
				//2^(N-i-1)の部分の余りが減る
				res = sumMinus;
				res -= remMinus[N-i-1];
				//余りが負になった場合の処理
				if(res < 0){
					res += minus;
				}
				res %= minus;

				//一度処理を行ったことを反映
				ans ++;
			}

			//残りの処理を行う
			ans += func(res);

			/*debug
			Console.WriteLine("res:{0},ans:{1}",res,ans);
			*/
			Console.WriteLine(ans);
		}

		//出力終了
		Console.Out.Flush();
	}
}



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

using u32 = uint32_t;

int main()
{
	std::string in;
	std::cin >> in;

	for(u32 i = 1; i<=in.size(); i++)
	{
		//std::cout << i << " = " << i%2 << " : " << in[i-1] << "\n";
		if(i%2 == 1)
		{
			if(!(in[i-1] == 'R' || in[i-1] == 'U' || in[i-1] == 'D'))
			{
				std::cout << "No\n";
				return 0;
			}
		}
		else if(i%2 == 0)
		{
			if(!(in[i-1] == 'L' || in[i-1] == 'U' || in[i-1] == 'D'))
			{
				std::cout << "No\n";
				return 0;
			}
		}
	}

	std::cout << "Yes\n";
	
	return 0;
}

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

const int INF = 1e9 + 1;

int N, M, L, Q;
vector<vector<int>> d, b;
int main() {
  cin >> N >> M >> L;
  d.resize(N, vector<int>(N, INF));
  b.resize(N, vector<int>(N, INF));

  rep(i, M) {
    int A, B, C;
    cin >> A >> B >> C;
    A--, B--;
    if (C > L) continue;
    d[A][B] = C;
    d[B][A] = C;
  }

  rep(i, N) d[i][i] = 0;

  rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

  rep(i, N) rep(j, N) {
    if (d[i][j] <= L) b[i][j] = 1;
  }
  rep(i, N) b[i][i] = 0;

  rep(k, N) rep(i, N) rep(j, N) b[i][j] = min(b[i][j], b[i][k] + b[k][j]);

  cin >> Q;
  rep(i, Q) {
    int s, t;
    cin >> s >> t;
    s--, t--;
    cout << (b[s][t] == INF ? -1 : b[s][t] - 1) << endl;
  }
  return 0;
}


Measured memory_bytes: 1280
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>
#include<map>
#include<queue>
#include<deque>
#include<fstream>
#include<random>

#define rep(i, n) for (ll i = 0; i < n; i++) 
#define rrep(i, n) for(ll i = n-1; i>=0; i--)
#define range(i, n, m) for (ll i = n; i < m; i++) 
#define rrange(i, n, m) for (ll i = n - 1; i => m; i--) 
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vp vector<pair<ll, ll> >
#define vvp vector<vector<pair<ll, ll> > >
#define First first
#define Second second.first
#define Third second.second
//#define MOD 998244353
#define MAX 100000

typedef long long int ll;
typedef unsigned long long int ull;

using namespace std;

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

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

	ll N;
	cin >> N;

	vl S(N);
	ll sum = 0;
	ll max = 0;
	rep(i, N) {
		cin >> S[i];
		sum += S[i];
	}

	if (sum % 10 == 0) {
		rep(i, N) {
			sum -= S[i];
			if (sum % 10 != 0) {
				chmax(max, sum);
			}
			sum += S[i];
		}
	}
	else {
		max = sum;
	}

	cout << max << endl;



	return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    s,w=MI()
    if w>=s:
        print("unsafe")
    else:
        print("safe")

main()


Measured memory_bytes: 61704
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.C_Challenge
{
    class ABC_049
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            string input = Console.ReadLine();
            var keys = new string[4] { "dream", "dreamer", "erase", "eraser" };
            while (input.Length > 0)
            {
                bool canErase = false;
                for (int i = 0; i < 4; i++)
                {
                    if (input.Length < keys[i].Length) continue;
                    if(input.Substring(input.Length - keys[i].Length,keys[i].Length)
                        .Equals(keys[i]))
                    {
                        canErase = true;
                        input = input.Substring(0, input.Length - keys[i].Length);
                    }
                }
                if (!canErase)
                {
                    Console.WriteLine("NO");
                    return;
                }
            }
            Console.WriteLine("YES");
        }
    }
}


Measured memory_bytes: 29860
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    base = 37; MOD = 10**9 + 9
    S = readline().strip()
    L = len(S)
    H = [0]*(L+1)
    pw = [1]*(L+1)
    ca = ord('a')
    v = 0
    for i in range(L):
        H[i+1] = v = (v * base + (ord(S[i]) - ca)) % MOD
    v = 1
    for i in range(1, L+1):
        pw[i] = v = v * base % MOD
    Q = int(readline())
    for i in range(Q):
        l, r, t = map(int, readline().split()); l -= 1
        m = r-l
        if ((H[r]-H[r-t]) - (H[l+t]-H[l]) * pw[m-t]) % MOD == 0:
            write("Yes\n")
            continue
        left = 0; right = m-t+1
        base = H[l] - H[l+t]
        while left+1 < right:
            mid = (left + right) >> 1
            if ((H[l+mid]-H[l+t+mid]) - base * pw[mid]) % MOD == 0:
                left = mid
            else:
                right = mid
        l1 = left
        left = 0; right = m-t-l1+1
        base = (H[r-t]-H[r]) % MOD
        while left+1 < right:
            mid = (left + right) >> 1
            if (H[r-t-mid]-H[r-mid]) * pw[mid] % MOD == base:
                left = mid
            else:
                right = mid
        l2 = left
        if l1+l2+1 == m-t:
            if l1 <= t or l2 <= t:
                write("Yes\n")
            else:
                write("No\n")
        else:
            if ((H[l+m-t-l2-1]-H[l+m-l2-1]) - (H[l+l1+1]-H[l+t+l1+1]) * pw[m-t-l2-l1-2]) % MOD != 0:
                write("No\n")
            else:
                p1 = l1; p2 = m-t-l2-1
                if p2 - p1 == t and S[l+p2-t] == S[l+p2+t]:
                    write("Yes\n")
                else:
                    write("No\n")
solve()


Measured memory_bytes: 14060
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define PUT(x) cout << x << endl
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };

int main(void)
{

	int k, t, answer = 0;
	cin >> k >> t;

	for (int i = 0; i < t; i++) {
		int a;
		cin >> a;

		if (a * 2 > k) {
			CHMAX(answer,a - (k-a) - 1);
		}
	}

	cout << answer << endl;

	return 0;
}


Measured memory_bytes: 256
import math
N = int(input())
x_list=[]
y_list=[]
dirsum=0
for i in range(N):
	x,y = input().split()
	x_list.append(int(x))
	y_list.append(int(y))
for i in range(N):
	for j in range(i+1,N):
		dirsum += math.sqrt(pow(x_list[i]-x_list[j],2)+pow(y_list[i]-y_list[j],2))
print(2*math.factorial(N-1)*dirsum/math.factorial(N))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define For(a,b,c) for(int a = b; a <= c; ++a)
#define Rof(a,b,c) for(int a = b; a >= c; --a)
#define Fv(a,b) for(auto &a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
#define ll long long
#define db double
#define sz(x) (ll)(x.size())
#define fasty ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pw2(i) (1ll << i)
#define bit(x,i) (x >> i & 1ll)
#define on(x,i) (x | (1ll << i))
#define off(x,i) ( x & (~(1ll << i)))
#define task "abc138_f"
template<typename T> void read(T &a)
{
    int c = getchar(), neg = 0;
    a = 0;
    while(c < '0' || c > '9') neg += (c == '-'), c = getchar();
    while(c <= '9' && c >= '0')
    {
        a = a * 10 + c - '0';
        c = getchar();
    }
    if(neg&1) a = -a;
}
template<typename T, typename... _T>
void read(T &a, _T& ...argc)
{
    read(a); read(argc...);
}

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define all(a) a.begin(), a.end()

typedef long long lint;

const lint mod = 1e9 + 7;

lint memo[61][2][2][2];

lint L, R;

lint solve(int pos, bool left, bool right, bool msb) {
    // printf("%d %d %d %d\n", pos, left, right, msb);
    if (pos == -1)
        return 1;
    lint &ret = memo[pos][left][right][msb];
    if (ret != -1)
        return ret;
    ret = 0LL;
    bool lb = (L & (1LL << pos)) ? false : true;
    bool rb = (R & (1LL << pos)) ? true : false;
    // x0, y0
    if (left || lb)
        ret += 1LL * solve(pos - 1, left, rb ? 1 : right, msb);
    // x0, y1
    if ((left || lb) && (right || rb) && msb)
        ret += 1LL * solve(pos - 1, left, right, msb);
    // x1, y1
    if (right || rb)
        ret += 1LL * solve(pos - 1, lb ? 1 : left, right, 1);
    ret %= mod;
    return ret;
}

main() {
    scanf("%lld%lld", &L, &R);
    memset(memo, -1, sizeof(memo));
    printf("%lld\n", solve(60, 0, 0, 0));
}


Measured memory_bytes: 256
#include<stdio.h>
  
int main(void){
    double  a,b,c,d,e,f,x,y;
 
    while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f) != EOF){
        x = (c*e-b*f)/(a*e-b*d);
        y = (c*d-a*f)/(b*d-a*e);
 
        if(x == -0.000){
            x = 0.000;
        }
        if(y == -0.000){
            y = 0.000;
        }
 
        printf("%.3lf %.3lf\n",x,y);
 
    }
    return 0;
}

Measured memory_bytes: 652
#!/usr/bin/env python
import bisect
from collections import defaultdict

def main():
    N = int(input())
    city_score_list = []
    for i in range(N):
        s, p = input().split()
        city_score_list.append((i, s, int(p)))

    city_score_list = sorted(city_score_list, key=lambda x: (x[1], -x[2]))
    for i, s, p in city_score_list:
        print(i+1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);

class mint{
    public:
        ll x;
        static unsigned long long mod;
        static unsigned long long mod_plus;
        mint(){x = 0;}
        mint(ll _x) : x((_x < 0 ? ((_x += mod_plus) < 0 ? _x + mod_plus : _x) : _x)%mod){}
        /*mint& operator=(const ll &a){
            x = a;
            return *this;
        }*/

        mint operator-(){
            return x == 0 ? 0 : mod - x;
        }
        mint& operator+=(const mint& a){
            if((x += a.x) >= mod) x -= mod;
            return *this;
        }
        mint operator+(const mint& a) const{
            mint res(*this);
            return res += a;
        }
        mint& operator-=(const mint& a){
            if((x -= a.x) < 0) x += mod;
            return *this;
        }
        mint operator-(const mint& a) const{
            mint res(*this);
            return res -= a;
        }
        mint& operator*=(const mint& a){
            (x *= a.x)%=mod;
            return *this;
        }
        /*mint& operator*=(const ll& a){
            mint temp(a);
            return *this *= temp;
        }*/
        mint operator*(const mint& a) const{
            mint res(*this);
            return res *= a;
        }
        /*mint operator*(const ll& a) const{
            mint res(*this);
            return res *= a;
        }*/
        mint pow(unsigned long long pw) const{
            mint res(1), comp(*this);
            while(pw){
                if(pw&1) res *= comp;
                comp *= comp;
                pw >>= 1;
            }
            return res;
        }
        //以下、modが素数のときのみ
        mint inv() const{
            mint res(*this);
            return res.pow(mod - 2);
        }
        mint& operator/=(const mint &a){
            (x *= a.inv().x)%=mod;
            return *this;
        }
        mint operator/(const mint &a) const{
            mint res(*this);
            return res /= a;
        }
};
ostream& operator<<(ostream& os, const mint& a){
    os << a.x;
    return os;
}
unsigned long long mint::mod = int(1e+9) + 7;
unsigned long long mint::mod_plus = (LLONG_MAX / mint::mod) * mint::mod;
typedef vector<mint> vm;

const ll MAX_N = ll(5e+5) + 10;
vm fact(MAX_N, mint(1));
void makefact(){
    reps(i,2,MAX_N) fact[i] = fact[i-1] * mint(i);
}
mint nCm(ll n, ll m){
    return fact[n] / (fact[n-m] * fact[m]);
}
mint pmt(ll n, ll m){
    return fact[n] / fact[n - m];
}

int main() {
    cin>>N>>M;
    makefact();
    mint res = pmt(M, N), sum(0);
    rep(k, N + 1){
        mint temp((k&1 ? -1 : 1));
        temp *= nCm(N, k) * pmt(M - k, N - k);
        sum += temp;
    }
    res *= sum;
    cout<<res<<endl;
}


Measured memory_bytes: 7004
#include<iostream>
using namespace std;
int main() {
    char b,a;
    cin >> b;
    if (b == 'A') a='T';
    if (b == 'T') a='A';
    if (b == 'C') a='G';
    if (b == 'G') a='C';
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Jewel ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
    Jewel;
    int n, i, mx=0;
    map<string,int>mp;
    vector<string>v;
    cin>>n;
    string s[n];
    for(i=0; i<n; i++)
    {
        cin>>s[i];
        mp[s[i]]++;
        mx = max(mx, mp[s[i]]);
    }
    for(i=0; i<n; i++)
    {
        if(mp[s[i]] == mx)
        {
            v.push_back(s[i]);
            mp[s[i]] = -1;
        }
    }
    sort(v.begin(), v.end());
    for(auto c : v)
        cout<<c<<endl;
    return 0;
}


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

int main(){
    ll n,k,a;
    scanf("%lld %lld",&n,&k);
//    cout << k << endl;
    vector<ll> tele(n);
    for(int i=0;i<n;i++) {
            scanf("%lld",&tele[i]); tele[i]--;
    }
    unordered_map<ll, ll> lastSeen;
    int cur = 0;
    while(k>0) {
        if(lastSeen.count(cur)) {
            ll diff = lastSeen[cur] - k;
            k %= diff;
            if(k==0) break;
        }
        lastSeen[cur] = k;
        k--;
        cur = tele[cur];
    }
    printf("%d\n", cur+1);
}


Measured memory_bytes: 11880
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <fstream>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007LL
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pll Dir[4] = {
	{ -1 ,0 },{ 0 , 1 },{ 1 ,0 },{ 0 ,-1 }
};

//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define INF 10000000000000000LL
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)

struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}

};
typedef vector<vector<Edge>> Graph;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll factorial(ll n) {//階乗
	ll ret = 1;
	rep(i,1, n + 1)
		ret = (ret *i)%MODU;

	return ret;
}

ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x %mod;
		x = x * x%mod;
		n >>= 1;
	}
	return res;
}
ll divmod(ll a, ll b, ll m) { // a/b(mod m)
								  // a/b (mod m)
								  // a*b^-1
								  // b^-1 * b = 1
								  // b^(m-1) = 1 
								  // b^(m-2) * b = 1
								  // b^-1 = b^(m-2)

								  // a/b = a * b^(m-2)

	return (a * 1LL * mod_pow(b, m - 2, m)) % m;
}
ll ncr(ll n, ll r) {
	return divmod(factorial(n) , (factorial(r) * (factorial(n - r)))%MODU, MODU);
}
signed main() {
	int n;
	string s;
	cin >> n >> s;

	if (s.substr(0, n / 2) + s.substr(0, n / 2) == s) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 2e12

int main(){
    int NV,NE;
    cin>>NV>>NE;
    long long int minimum[NV][NV];
    fill(minimum[0],minimum[NV],INF);
    for(int i=0;i<NE;i++){
        int s,t,d;
        cin>>s>>t>>d;
        minimum[s][t]=d;
    }
    bool update;
    for(int i=0;i<NV;i++)minimum[i][i]=0;
    for(int k=0;k<NV;k++){
        for(int i=0;i<NV;i++){
            for(int j=0;j<NV;j++){
                if(minimum[i][k]==INF||minimum[k][j]==INF)continue;
                minimum[i][j]=min(minimum[i][j],minimum[i][k]+minimum[k][j]);
            }
        }
    }
    for(int i=0;i<NV;i++){
        if(minimum[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }    

    for(int i=0;i<NV;i++){
        for(int j=0;j<NV;j++){
            if(minimum[i][j]==INF){
                cout<<"INF";
            }else{
                cout<<minimum[i][j];
            }
            if(j+1!=NV)cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3180
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<utility>

using namespace std;

int main()
{
    int n,i,low,high,c;
    scanf("%d",&n);
    int p[n];
    for(i=0; i<n; i++)
    {
        scanf("%d",&p[i]);
    }
    low=high=p[0];
    for(i=0; i<n; i++)
    {
        if(low>p[i])
            low=p[i];
        if(high<p[i])
            high=p[i];
    }
    c=high-low;
    printf("%d\n",c);
    return 0;
}


Measured memory_bytes: 256
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;

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

    int a, b, c;
    cin >> a >> b >> c;

    if (a + b == c || a + c == b || b + c == a) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
A,B,C,D=map(int,input().split())
P='R'*(C-A)
P+='U'*(D-B)
P+='L'*(C-A)
P+='D'*(D-B+1)
P+='R'*(C-A+1)
P+='U'*(D-B+1)
P+='L'
P+='U'
P+='L'*(C-A+1)
P+='D'*(D-B+1)
print(P+'R')

Measured memory_bytes: 61728
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
#適当な整数iを考えたとき、i-1の数字が余っているのであれば、それとペアを組ませるのが最適。
#余っていない時は、出来るだけ自分同士でペアを組む。もし一枚余るようであれば、残しておく
ans, a[0] = divmod(a[0], 2)
for i in range(1,n):
    pair = 0
    if a[i-1] > 0:
        pair = min(a[i-1], a[i])
        a[i-1] -= pair
        a[i] -= pair
    ans += pair
    pair, a[i] = divmod(a[i], 2)
    ans += pair
print(ans)

Measured memory_bytes: 50648
import Control.Applicative

type Problem = (Int, Int)
type Result = [String]

slove :: Problem -> Result
slove (h, w) = (replicate 1 (paintLine w)) ++ (replicate (h - 2) (paintRoom w)) ++ (replicate 1 (paintLine w))

paintLine :: Int -> String
paintLine w = concat . replicate w $ "#"

paintRoom :: Int -> String
paintRoom w = "#" ++ (concat.replicate (w - 2) $ ".") ++ "#"  

input :: IO Problem
input = do 
        [h, w] <- map (read :: String -> Int).words <$> getLine
        return (h, w)

output :: Result -> IO ()
output xs = putStrLn $ concat [x ++ "\n" | x <- xs]

main :: IO ()
main = do 
         xs <- input
         if (xs == (0,0))
           then return ()
           else do
            output $ slove xs
            main

Measured memory_bytes: 4080
#include <stdio.h>
#include <stdlib.h>
#define max_size (int)(1e5 + 1)

typedef struct {
	int N;
	int *u;
	int *u_rank;
}union_find;

union_find *make_union_find(int N){
	int i;
	union_find *uf = (union_find *)malloc(sizeof(union_find));
	uf->N = N;
	uf->u = (int *)malloc(sizeof(int) * N);
	uf->u_rank = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		(uf->u)[i] = i;
		(uf->u_rank)[i] = 1;
	}
	return uf;
}

int root_uf(int x, union_find *uf){
	int *u = uf->u;
	if(u[x] == x){
		return x;
	}
	else{
		u[x] = root_uf(u[x], uf);
		return u[x];
	}
}

void combine_uf(int x, int y, union_find *uf){
	int x_root = root_uf(x, uf);
	int y_root = root_uf(y, uf);
	int *u = uf->u;
	int *u_rank = uf->u_rank;
	if(x_root == y_root){
		return;
	}
	else if(u_rank[x_root] < u_rank[y_root]){
		u[x_root] = y_root;
		u_rank[y_root] += u_rank[x_root];
		u_rank[x_root] = 0;
	}
	else{
		u[y_root] = x_root;
		u_rank[x_root] += u_rank[y_root];
		u_rank[y_root] = 0;
	}
}

//xとyが同じ集合に属していれば1を,そうでなければ0を返す
int is_same_union_uf(int x, int y, union_find *uf){
	if(root_uf(x, uf) == root_uf(y, uf)){
		return 1;
	}
	else{
		return 0;
	}
}

//xが属する集合の要素数を返す
int rank_uf(int x, union_find *uf){
	return (uf->u_rank)[root_uf(x, uf)];
}

int main(){
	int L, N, l, r, i;
	char *S = (char *)malloc(sizeof(char) * max_size);
	scanf("%s", S);
	for(i = 0; S[i] != '\0'; i++){}
	L = i;
	union_find *uf = make_union_find(L + 1);
	uf->u_rank[0] = ((int)S[0] - (int)'a') % 26;
	for(i = 1; i < L; i++){
		uf->u_rank[i] = ((int)S[i] - (int)S[i - 1] + 26) % 26;
	}
	uf->u_rank[L] = ((int)'a' - (int)S[L - 1] + 26) % 26;
	for(i = 0; i <= L / 2; i++){
		combine_uf(i, L - i, uf);
	}
	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%d%d", &l, &r);
		combine_uf(l - 1, r, uf);
	}
	for(i = 0; i <= L; i++){
		if(rank_uf(i, uf) % 26 != 0){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 1152
n,m,x,y=map(int,input().split())
a=map(int,input().split())
b=map(int,input().split())
A=max(a)
B=min(b)
D=0
for w in range(A+1,B+1):
 if x<w<=y:
  D+=1

if D>=1:
 print ("No War")
else:
 print("War")

Measured memory_bytes: 3064
import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
cnta = [0 for i in range(n + 1)]
cntb = [0 for i in range(m + 1)]

for i in range(n):
    cnta[i + 1] = cnta[i] + a[i]
for i in range(m):
    cntb[i + 1] = cntb[i] + b[i]
for i in range(n + 1):
    cnt = 0
    if k - cnta[i] >= 0:
        cnt = i
        cnt += min(m, bisect.bisect_right(cntb, k - cnta[i]) - 1)
    ans = max(ans, cnt)
print(ans)


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

using namespace std;

// (weighted) UnionFind
class UnionFind {
    public:
        UnionFind(int n) : mPar(n), mRnk(n,0), mWeight(n,0) {
            for(int i = 0; i < n; ++i) mPar[i] = i;
        }

        int find(int x){
            if(mPar[x]==x) return x;
            int r = find(mPar[x]); // 経路圧縮
            mWeight[x] += mWeight[mPar[x]]; // 一つ上の親からの累積和
            return mPar[x] = r;
        }

        bool same(int x,int y){
            return find(x) == find(y);
        }

        int weight(int x){
            find(x); // 経路圧縮
            return mWeight[x];
        }

        int diff(int x, int y){
            return weight(y) - weight(x);
        }

        void unite(int x,int y, int w = 0){
            w += weight(x); w -= weight(y);
            x = find(x);
            y = find(y);
            if(x==y) return;
            if(mRnk[x] < mRnk[y]) swap(x,y), w = -w;
            mPar[y] = x;
            mWeight[y] = w;
            if(mRnk[x] == mRnk[y]) ++mRnk[x];
        }

    private:
        vector<int> mPar, mRnk, mWeight;
};

int main(){
    int n,q,x,y,z;
    cin >> n >> q;
    UnionFind uf(n);
    for(int i = 0; i < q; ++i){
        cin >> x >> y >> z;
        --x;--y;
        if(!uf.same(x,y)){
            uf.unite(x,y,z);
        } else {
            if(z!=uf.diff(x,y)){
                cout << "No" << '\n';
                return 0;
            }
        }
    }
    cout << "Yes" << '\n';
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstdlib>
#include <vector>
using namespace std;



int main() {

	int st[110];
	int top = 0;

	char str[110];
	while (scanf("%s", str) != EOF) {

		int a, b;
		if (str[0] == '+') {
			a = st[top--];
			b = st[top--];
			st[++top] = b + a;
		}
		else if (str[0] == '-') {
			a = st[top--];
			b = st[top--];
			st[++top] = b - a;
		}
		else if (str[0] == '*') {
			a = st[top--];
			b = st[top--];
			st[++top] = b * a;
		}
		else {
			st[++top] =atoi(str);
		}
	}

	cout << st[top] << endl;

	return 0;
}



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

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

int main(void)
{
    int N, K;
    cin >> N;
    cin >> K;
    int h[N];
    rep(i, N) cin >> h[i];

    int count = 0;
    for (int i = 0; i < N; i++)
    {
        if (h[i] >= K)
        {
            count = count + 1;
        }
    }

    printf("%d", count);
    return 0;
}

Measured memory_bytes: 640