akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int N,K,cur=0; string S; cin>>N>>K>>S;
	for (int i=1; i<N; i++)
		cur+=int(S[i]==S[i-1]);
	cout<<min(N-1,cur+2*K)<<"\n";
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll H,W,m;
    cin >> H >> W >> m;
    vector<ll>h,w;
    for(ll i=0;i<m;i++){
        ll x,y;
        cin >> x >> y;
        x--;y--;
        h.push_back(x);
        w.push_back(y);
    } 
    vector<ll>c(H,0),d(W,0);
    for(ll i=0;i<m;i++){
        c[h[i]]++;
        d[w[i]]++;
    }

    ll cm=-MOD,dm=-MOD;
    for(ll i=0;i<H;i++) cm=max(cm,c[i]);
    for(ll i=0;i<W;i++) dm=max(dm,d[i]);
    ll ans=cm+dm;
    
    ll cj=0,dj=0;
    for(ll i=0;i<H;i++){
        if(c[i]==cm) cj++;
    }
    for(ll i=0;i<W;i++){
        if(d[i]==dm) dj++;
    }
    ll M=0;
    for(ll i=0;i<m;i++){
        if(c[h[i]]==cm&&d[w[i]]==dm) M++;
    }
    if(M==cj*dj){
        ans--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 12656
#include <bits/stdc++.h>
#include <iomanip>
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
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

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


int main(){
    cin>>A;
    N = A / 100;
    K = A % 100;
    cout<<(N*5 < K ? 0 : 1)<<endl;
}

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

using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr i64 INF = std::numeric_limits<i64>::max()/2;


struct S {
	i64 a;
	i64 b;
};

int main()
{
	std::ios_base::sync_with_stdio(0);
	
	i64 h, n;

	std::cin >> h >> n;

	std::vector<S> v(n);

	for(i64 i=0; i<n; ++i)
	{
		i64 a, b;
		std::cin >> a >> b;
		v[i] = {a, b};
	}
	
	i64 dp[h+10005];
	dp[0]=0;
	for(i64 i=1;i<h+10005;++i)
	{
		dp[i]=INF;
	}

	for(i64 i=0;i<h+10005;++i)
	{
		for(i64 j=0;j<n;++j)
		{
			if(v[j].a <= i)
			{
				dp[i] = std::min(dp[i], dp[i-v[j].a]+v[j].b);
			}	
		}
	}

	i64 ans = dp[h];

	for(i64 i=h+1;i<h+10005; ++i)
	{
		if(dp[i] < ans)
		{
			ans = dp[i];
		}
	}

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

Measured memory_bytes: 384
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = [int(_) for _ in input().split()]
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
    if b == 1:
        print(1)
        exit()
print(b)


Measured memory_bytes: 14224
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
using namespace std;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
const double pi = acos(-1.0);
int read()
{
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret;
}
ll q,h,s,d,n;
struct node
{
	double avg;
	ll w,v;
} a[4]; 
ll ans;
bool cmp(node x,node y)
{
	if(x.avg==y.avg)
	return x.w>y.w;
	return x.avg<y.avg;
}
int main()
{
 	#ifdef TEST
	 	freopen("input.txt","r",stdin);
	#endif
	ans=0;
	scanf("%I64d%I64d%I64d%I64d%I64d",&q,&h,&s,&d,&n);
	n*=4;
	a[0].avg=(double)q*4.0,a[0].w=1,a[0].v=q;
	a[1].avg=(double)h*2.0,a[1].w=2,a[1].v=h;
	a[2].avg=(double)s,a[2].w=4,a[2].v=s;
	a[3].avg=(double)d/2.0,a[3].w=8,a[3].v=d;
	sort(a,a+4,cmp);
	for(int i=0;i<4&&n;i++)
	{
		if(n>=a[i].w)
		{
			ans+=a[i].v*(ll)(n/a[i].w);
			n%=a[i].w;
		}
	}
	printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))

cnt = 0
s = 0
for i in range(n):
    #偶数インデックスをプラスにする
    s+=a[i]
    if i%2 and s>=0:
        cnt+=s+1
        s = -1
    elif i%2==0 and s<=0:
        cnt+=1-s
        s = 1
ans = cnt
cnt = 0
s = 0
for i in range(n):
    #偶数インデックスをマイナスにする
    s+=a[i]
    if i%2==0 and s>=0:
        cnt+=s+1
        s = -1
    elif i%2 and s<=0:
        cnt+=1-s
        s = 1
ans = min(ans,cnt)
print(ans)

Measured memory_bytes: 14464
#include<cstdio>
int main(){
    double ps[4][2];
    for(;;){
        for(int i=0;i<4;i++){
            for(int j=0;j<2;j++){
                if(scanf("%lf",&ps[i][j])==-1)return 0;
            }
        }
        if((ps[0][0]-ps[1][0])*(ps[2][0]-ps[3][0])+(ps[0][1]-ps[1][1])*(ps[2][1]-ps[3][1])==0)printf("YES\n");
        else printf("NO\n");
    }
}

Measured memory_bytes: 0
N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, d))
    edges[to].append((fr, d))

minDist = [10**18] * N
st = [(0, 0)]
while st:
    now, dist = st.pop()

    if minDist[now] < dist:
        continue
    minDist[now] = dist

    for to, d in edges[now]:
        if minDist[to] > dist + d:
            st.append((to, dist + d))

for i in range(N):
    print(0 if minDist[i] % 2 == 0 else 1)


Measured memory_bytes: 42820
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<complex>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 1000 * 100 + 47;

LL A[MAX];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	LL ans = 0;
	FOR(i, 0, n)
	{
		cin >> A[i];
		int tmp = A[i] / 2;
		bool two = A[i] != 0 && A[i] % 2 == 0;
		//cout << i << ":" << two << endl;
		ans += two ? tmp - 1 : tmp;
		
		if (two)
		{
			A[i] = 2;
			continue;
		}

		A[i] %= 2;
	}

	//FOR(i, 0, n) cout << A[i] << " ";
	//cout << endl;

	if (A[0] == 2)
	{
		A[0] = 0;
		ans++;
	}

	FOR(i, 1, n)
	{
		if (A[i] != 0 && A[i - 1] != 0)
		{
			ans++;
			A[i]--;
			A[i - 1]--;
		}

		if (A[i] == 2)
		{
			ans++;
			A[i] = 0;
		}
	}

	cout << ans << endl;
}

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

ll dp[100009][4];
ll n, a[100009],b[100009],c[100009];

ll solve(int idx, int prev)
{
    if(idx == n)
        return 0;

    if(dp[idx][prev] != -1)
        return dp[idx][prev];

    ll ans = INT_MIN;

	if(prev == 0) {
		ans = max(ans, b[idx] + solve(idx + 1, 1));
		ans = max(ans, c[idx] + solve(idx + 1, 2));
	} 
    else if(prev == 1) {
		ans = max(ans, a[idx] + solve(idx + 1, 0));
		ans = max(ans, c[idx] + solve(idx + 1, 2));
	} 
    else if(prev == 2) {
		ans = max(ans, b[idx] + solve(idx + 1, 1));
		ans = max(ans, a[idx] + solve(idx + 1, 0));
	}
     else {
		ans = max(ans, c[idx] + solve(idx + 1, 2));
		ans = max(ans, b[idx] + solve(idx + 1, 1));
		ans = max(ans, a[idx] + solve(idx + 1, 0));
	}
 
	return dp[idx][prev] = ans;
}

int main() {

    cin >> n;
    memset(dp, -1, sizeof(dp));

    for(int i=0; i<n; i++)
        cin>> a[i] >> b[i] >> c[i];

    ll ans = solve(0,3);

    cout<< ans <<endl;


}

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

#define ln '\n'
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, l;
    cin >> n >> l;

    int target = 1e9;
    int sum = 0;
    REP(i, n) {
        if (abs(i + l) < abs(target)) target = i + l;
        sum += i + l;
    }

    cout << sum - target << ln;
    return 0;
}


Measured memory_bytes: 256
'use strict'

const count = (item, array) => {
    let rec = 0
    for(let val of array){
        if(val === item){
            rec++
        }
    }
    return rec
}

const main = (input) => {
    input = input.split('\n')
    const N = parseInt(input[0])
    const Ns = input.slice(1, N + 1)
    const M = parseInt(input[N + 1])
    const Ms = input.slice(N + 2, N + M + 2)

    let earn = 0
    Ns.forEach(v => {
        let Nhas = count(v, Ns)
        let Mhas = count(v, Ms)
        let diff = Nhas - Mhas
        if(diff > earn) {
            earn = diff
        }
    })
    console.log(earn)
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

Measured memory_bytes: 8368
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    bool b = true;
    cin >> n;
    vector<long> v(n);
    for(int i=0;i<n;i++)cin >> v[i];
    v[0]--;
    for(int i=1;i<n;i++){
        if(v[i] > v[i-1])v[i]--;
        else if(v[i] < v[i-1]){
            cout << "No" << endl;
            b = false;
            break;
        }
    }
    if(b)cout << "Yes" << endl;
}

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

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> v(N), w(N);
    for (int i=0; i<N; ++i) cin >> v[i] >> w[i];

    vector<int> dp(W+1, 0);
    for (int i=0; i<N; ++i) {
        for (int j=W-w[i]; j>=0; --j) {
            dp[j+w[i]] = max(dp[j+w[i]], dp[j]+v[i]);
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}


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

int main() {  
  int n,m; cin>>n>>m;
  vector<int> sum(n);
  vector<int> a(2);
  for(int i=0;i<m;i++){
    cin>>a[0]>>a[1];
    sum[a[0]-1]++;
    sum[a[1]-1]++;
  }
  for(int j=0;j<n;j++)
    cout<<sum[j]<<endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

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

  int n;
  cin >> n;

  int d[n + 1];
  fill(d, d + n + 1, 0);

  d[1] = 1;
  for(int i = 2; i <= n; i++){
    int m = i;
    for(int j = 2; j <= m; j++){
      while(m % j == 0){
        ++d[j];
        m /= j;
      }
    }
  }

  int dp[n + 1][76];
  for(int i = 0; i < n + 1; i++){
    fill(dp[i], dp[i] + 76, 0);
  }

  dp[1][1] = 1;
  for(int i = 2; i <= n; i++){
    for(int j = 1; j <= 75; j++){
      for(int k = 0; k <= d[i]; k++){
        if(j % (k + 1) == 0){
          dp[i][j] += dp[i - 1][j / (k + 1)];
        }
      }
    }
  }

  cout << dp[n][75] << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=55;
int n,m,vis[maxn];
bool g[maxn][maxn];
struct nod{
	int x,y;
}node[1300];
void dfs(int star){
	vis[star]=1;
	int i;
	for(i=1;i<=n;i++){
		if(vis[i]==0&&g[star][i]==1){
			dfs(i);
		}
	}
	return ;
}
int main(){
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF){
		int ans=0;
		memset(g,0,sizeof(g));
		for(i=0;i<m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			node[i].x=x;
			node[i].y=y;
			g[x][y]=g[y][x]=1;
		}
		for(i=0;i<m;i++){
			memset(vis,0,sizeof(vis));
			g[node[i].x][node[i].y]=g[node[i].y][node[i].x]=0;
			dfs(1);
			g[node[i].x][node[i].y]=g[node[i].y][node[i].x]=1;
			bool bridge=false;
			for(j=1;j<=n;j++){
				if(!vis[j])
					bridge=true;
			}
			if(bridge)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 128
// Problem : D - Anything Goes to Zero
// Contest : AtCoder - AIsing Programming Contest 2020
// URL : https://atcoder.jp/contests/aising2020/tasks/aising2020_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define int long long
#define ios std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mii map<int, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=(int)x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
using namespace std;
int gcd(int x, int y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
int power(int x, int y, int MOD)  
{  
    int res = 1;
    x = x % MOD;
    if (x == 0) return 0;
  	if(y==0) return 1;
    while (y > 0)  
    { 
        if (y & 1)  
            res = (res*x) % MOD;
        y = y>>1;
        x = (x*x) % MOD;  
    }  
    return res;  
}
int fun(int n)
{
	if(n==0)return 0;
	int ans=1;
	ans+=fun(n%setbits(n));
	return ans;
}
void solve()
{
	int n;
	string x;
	cin>>n>>x;
	int z=count(all(x),'1');
	int z1=0,z2=0;
	if(z==0){
		rep(i,0,n){
			cout<<1<<endl;
		}
		return;
	}
	if(z==1){
		if(x[n-1]=='1')z2=1;
		for(int i=0;i<n;i++){
			if(x[i]=='1'){
				cout<<0<<endl;
			}
			else{
				if(i==n-1)
				cout<<2<<endl;
				else
				cout<<z2+1<<endl;	
			}
		}
		return;
	}
	for(int i=0;i<n;i++){
		if(x[n-1-i]=='1'){
			z1=(z1+power(2,i,z-1))%(z-1);
			z2=(z2+power(2,i,z+1))%(z+1);
		}
	}
	
	for(int i=0;i<n;i++){
		int ans=0;
		if(x[i]=='1'){
			int kk=(((z1-power(2,n-1-i,z-1))%(z-1)+z-1)%(z-1));
			cout<<fun(kk)+1<<endl;
		}
		else{
			int kk=((z2+power(2,n-1-i,z+1))%(z+1)+z+1)%(z+1);
			cout<<fun(kk)+1<<endl;		
		}
	}
}

int32_t main()
{	
	ios;
	int t=1; 
	//cin>>t;
	while(t--) solve();
}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define Mod 998244353
#define pi 3.14159265358979323846
#define endl '\n'
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;

const int N=1e5+5;
vector<ll> freq(N);

int main()
{
    ll sum=0;
    int n;
    cin>>n;
    vll a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        freq[a[i]]++;
        sum+=a[i];
    }

    int q;
    cin>>q;
    while(q--)
    {
        ll b,c;
        cin>>b>>c;
        ll p=freq[b];
        freq[b]=0;
        freq[c]+=p;
        sum+=(ll)p*(c-b);
        cout<<sum<<endl;
    }

    return 0;
}



Measured memory_bytes: 4832
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static int cnt = 0;
	static PrintWriter out =new PrintWriter(System.out);
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	
    	int n = sc.nextInt();
    	int array[] = new int[n];
    	for(int i=0;i<n;i++) {
    		array[i] = sc.nextInt();
    	}
    	bubble(array);
    	out.print(array[0]);
    	for(int i=1;i<n;i++) {
    		out.print(" "+array[i]);
    	}
    	out.println();
    	out.println(cnt);
    	out.flush();
    }
    
    static void bubble(int[] a) {
    	for(int i=0;i<a.length;i++) {
    		for(int j=a.length-1;j>=i+1;j--) {
    			if(a[j]<a[j-1]) {
    				int temp = a[j];
    				a[j] = a[j-1];
    				a[j-1] =temp;
    				cnt++;
    			}
    				
    		}
    	}
    }
    	
}


Measured memory_bytes: 26440
#include <iostream>
#include <queue>

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

using ll = long long;

int main() {
    ll ans = 0LL;
    ll n, m, a;
    std::priority_queue< ll > que;
    std::cin >> n >> m;
    REP(i, n) {
        std::cin >> a;
        que.push( a );
    }
    REP(i, m) {
        a = que.top(); que.pop();
        a /= 2;
        que.push( a );
    }

    while (!que.empty()) {
        ans += que.top(); que.pop();
    }
    std::cout << ans << std::endl;
    return 0;
}



Measured memory_bytes: 1400
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pii pair<ll,ll>
#define tii tuple<ll,ll,ll>
#define all(v) (v).begin(),(v).end()
#define ll long long
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define ld long double
#define mod 998244353
#define PI 3.141592653589793238
#define phi 1.638
#define eps 1e-9
//#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;   


int main() 
{ 
    string s;
    cin>>s;
    int n = s.length();
    for(int i = 0; i<n; ++i) {
        if(s[i]=='?')
            s[i] = 'D';
    }
    cout<<s<<endl;
} 

Measured memory_bytes: 3752
#include<iostream>
#include<algorithm>
int N;
int A[100010];
int main() {
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		std::cin >> tmp;
		A[tmp]++;
		A[tmp + 1]++;
		A[tmp + 2]++;
	}
	int ans = 0;
	for (auto u:A) {
		ans = std::max(ans, u);
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=10010;
struct Node
{
    int to;
    int dis,cost;
};
vector<Node> g[N];
int dist[N];
int cost[N];
bool vis[N];
int n,m;

void dijkstra()
{
    memset(vis,0,sizeof vis);
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    dist[1]=0;
    cost[1]=0;
    heap.push({0,1});

    while(heap.size())
    {
        int x=heap.top().second;
        heap.pop();

        if(vis[x]) continue;
        vis[x]=true;

        for(int i=0;i<g[x].size();i++)
        {
            Node e=g[x][i];
            int j=e.to,w=e.dis,c=e.cost;
            if(dist[j] > dist[x] + w || (dist[j] == dist[x] + w && c < cost[j]))
            {
                dist[j]=dist[x]+w;
                cost[j]=c;
                heap.push({dist[j],j});
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(!n && !m) break;

        for(int i=1;i<=n;i++) g[i].clear();

        while(m--)
        {
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            g[a].push_back({b,c,d});
            g[b].push_back({a,c,d});
        }

        dijkstra();

        int ans=0;
        for(int i=2;i<=n;i++)
            ans+=cost[i];

        cout<<ans<<endl;
    }

    // system("pause");
}



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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

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

//最大公約数 
 ll gcd(ll a,ll b){
 if(b == 0) return a;
 return gcd(b,a%b);
 }

//最小公倍数
 ll lcm(ll a,ll b){
 ll g = gcd(a,b);
 return a / g * b; // Be careful not to overflow  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
} 







int main(){
int A, B, C;
cin >> A >> B >> C;

for(int i = 1; i <= B; i++){
  if(A * i % B == C){
    YES;
    return 0;
  }
}

NO;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct bnode{
    int key;
    struct bnode *parent;
    struct bnode *left;
    struct bnode *right;
}BinNode;
 
typedef struct btree{
    BinNode *bn;
    BinNode *root;
    int size;
}BinTree;
 
BinNode initBinNode(int);
void Insert(BinTree *, BinNode *);
void InorderPrint(BinNode *);
void PreorderPrint(BinNode *);
 
int main(void){
    int m, k;
    char s[10];
    int i;
 
    BinTree t;
    BinTree *T = &t;
    T->root = NULL;
    T->size = 0;
 
    scanf("%d", &m);
    T->bn = calloc(m, sizeof(BinNode));
    for (i = 0; i < m; i++){
        scanf("%s", s);
        if (!strcmp(s, "insert")){
            scanf("%d", &k);
            T->bn[T->size] = initBinNode(k);
            BinNode *z = &(T->bn[T->size]);
            T->size++;
            Insert(T, z);
        }
        else if (!strcmp(s, "print")){
                InorderPrint(T->root);
                printf("\n");
                PreorderPrint(T->root);
                printf("\n");
        }
    }
 
    return 0;
}
 
 
BinNode initBinNode(int v){
    BinNode z;
    z.key = v;
    z.parent = NULL;
    z.left = NULL;
    z.right = NULL;
 
    return z;
}
 
void Insert(BinTree *T, BinNode *z){
    BinNode *x, *y;
 
    y = NULL;
    x = T->root;
    while (x != NULL){
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
 
    if (y == NULL)
        T->root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
}
 
void InorderPrint(BinNode *p){
    if (p != NULL){
        InorderPrint(p->left);
        printf(" %d", p->key);
        InorderPrint(p->right);
    }
}
 
void PreorderPrint(BinNode *p){
    if (p != NULL){
        printf(" %d", p->key);
        PreorderPrint(p->left);
        PreorderPrint(p->right);
    }
}

Measured memory_bytes: 16236
#include<bits/stdc++.h>
#define ll long long
#define INF 1999122700
using namespace std;
int n;
int a[200004],f[200004];
map<int,int>mert;
bool check(int len,int x){
    return (mert[len-1]>=x);
}
int main(){
    mert.clear();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    f[1]=1;
    mert[0]=INF;
    mert[1]=a[1];
    int res=1;
    for(int i=2;i<=n;i++){
        int mid,L=1,R=res+1,ans=1;
        while(L<=R){
            mid=(L+R)>>1;
            if(check(mid,a[i])){
                ans=mid;
                L=mid+1;
            }
            else R=mid-1;
        }
        if(!mert.count(ans))mert[ans]=a[i];
        else mert[ans]=max(mert[ans],a[i]);
        f[i]=ans;
        res=max(res,ans);
    }
    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using G = vector<vector<int>>;
    
int main(){
    int r, c, k;
    cin >> r >> c >> k;
    vector<vector<ll>> val(r, vector<ll>(c));
    rep(i,k){
        int a, b;
        ll v;
        cin >> a >> b >> v;
        a--; b--;
        val[a][b] = v;
    }


    vector<vector<vector<ll>>> dp(r, vector<vector<ll>>(c, vector<ll>(4)));

    ll ans = 0;
    
    rep(i,r){
        rep(j,c){
            if(i==0 && j==0){
                if(val[i][j]!=0) {
                    dp[i][j][1] = val[i][j];
                    ans = max(ans, dp[i][j][1]);
                }
            } else if(i==0){
                for(int k=0; k<=3; k++){
                    if(k==0) ans = max(ans, dp[i][j][k]); 
                    else if(val[i][j]==0) dp[i][j][k] = dp[i][j-1][k];
                    else dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1]+val[i][j]);
                    ans = max(ans, dp[i][j][k]);
                }
            } else{
                rep(k,4){
                    ll above = *max_element(dp[i-1][j].begin(),dp[i-1][j].end());
                    if(j==0){
                        if(k==0) dp[i][j][k] = above;
                        else if(k==1 && val[i][j]!=0){
                            dp[i][j][1] = above + val[i][j];
                        }
                        ans = max(ans, dp[i][j][k]);
                    } else{
                        if(k==0) dp[i][j][k] = max(dp[i][j-1][k], above);
                        else if(k==1){
                            if(val[i][j]==0) dp[i][j][k] = dp[i][j-1][k];
                            else {
                                dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1]+val[i][j]);
                                dp[i][j][k] = max(dp[i][j][k], above+val[i][j]);
                            }
                        } else{
                            dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1]+val[i][j]);
                        }
                        ans = max(ans, dp[i][j][k]);
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string& s, int lim=256) { // or basic_string<int>
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		rep(i,1,n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
					s[i + k] == s[j + k]; k++);
	}
};

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    
    SuffixArray sa(s);
    int lo = 0;
    int hi = n;

    /*
    cout << "SA:";
    for (int i = 0; i <= n; ++i) {
        cout << " " << sa.sa[i];
    }
    cout << '\n';

    cout << "LCP:";
    for (int i = 0; i <= n; ++i) {
        cout << " " << sa.lcp[i];
    }
    cout << '\n';
    */

    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;

        bool found = false;
        for (int i = 1; i <= n; ++i) {
            int first = sa.sa[i];
            int last = sa.sa[i];
            int j = i;
            while (j + 1 <= n and sa.lcp[j + 1] >= mid) {
                ++j;
                first = min(first, sa.sa[j]);
                last = max(last, sa.sa[j]);
            }

            i = j;

            if (first + mid <= last) {
                found = true;
                break;
            }
        }

        if (found) {
            lo = mid;
        } else {
            hi = mid;
        }
    }

    cout << lo << '\n';
    
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
        int n, d[50];
        int i, j;
        int total;

        scanf("%d", &n);

        total=0;
        scanf("%d", &d[0]);

        for(i=1; i<n; i++){
                scanf("%d", &d[i]);

                for(j=0; j<i; j++){
                        total += d[j] * d[i];
                }
        }

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

        return 0;
}

Measured memory_bytes: 128
// luogu-judger-enable-o2
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=2*1e5+5,inf=1e9+5;;
int n;
LL A,B=inf,_A,_B=inf,ans;
int in[N],ou[N],cnt;
struct card {LL val,bag;} b[N<<1];
bool cmp(card u,card v)
{
	return u.val<v.val;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&b[i*2-1].val,&b[i*2].val);
		b[i*2-1].bag=b[2*i].bag=i;
		if(b[i*2-1].val>b[i*2].val) swap(b[i*2-1],b[i*2]);
		A=max(b[i*2].val,A),B=min(b[i*2].val,B);
		_A=max(b[i*2-1].val,_A),_B=min(b[i*2-1].val,_B);
	}
	ans=(A-B)*(_A-_B);
	//cout<<ans<<" "<<A-_B<<endl;
	sort(b+1,b+n*2+1,cmp);
	//for(int i=1;i<=n<<1;++i) cout<<b[i].val<<" "<<b[i].bag<<endl;
	int l=2,r=2;
	while(r<=n*2)
	{
		while(cnt<n && r<=n*2) cnt+=(in[b[r].bag]==0),++in[b[r++].bag];
		if(r>2*n) break;
		while(in[b[l].bag]==2) --in[b[l].bag],++ou[b[l++].bag];
		ans=min(ans,(b[r-1].val-b[l].val)*(A-_B));
		//cout<<l<<" "<<r<<" "<<b[l].val<<" "<<b[r].val<<endl;
		if(ou[b[l].bag]==1) break;
		++ou[b[l].bag],--in[b[l].bag],++l,--cnt;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 8064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String args[]) {
		ConsoleScanner cin = new ConsoleScanner();
		PrintWriter cout = new PrintWriter(System.out);
		solve(cin, cout);
		cout.flush();
	}

	private static void solve(ConsoleScanner cin, PrintWriter cout) {
		// example();

		// 二分法
		// ただし初期のleft, rightが特殊

		long l = 1;
		Long firstYy = null;
		for (; l <= (long) 1e10; l *= 10) {
			cout.println("? " + l);
			cout.flush();
			String ans = cin.next();
			if ("N".equals(ans))
				break;
			cout.println("? " + (l + 1));
			cout.flush();
			String ans2 = cin.next();
			if ("N".equals(ans2))
				continue;
			if (firstYy == null)
				firstYy = l;
		}
		if (l == (long) 1e11) {
			cout.println("! " + firstYy);
			return;
		}
		long r = l * 10 - 1;
		while (l + 1 != r) {
			long m = (l + r) / 2;
			cout.println("? " + m);
			cout.flush();
			String ans = cin.next();
			switch (ans) {
			case "Y":
				r = m;
				break;
			case "N":
				l = m;
				break;
			default:
				throw new IllegalStateException();
			}
		}
		long N = r / 10;
		cout.println("! " + N);
	}

	static void example() {
		// Nより小さい桁ではYYY...NNN
		// Nより同じ桁では全てY
		// Nより大きい桁ではNNN...YYY

		// N=50とN=51の差は？
		// ? 500 ~ ? 509の回答がY/Nになる
		for (int N : new int[] { 1, 7, 9, 10, 11, 50, 51, 99, 100 }) {
			String strN = Integer.toString(N);
			LinkedHashMap<Integer, Character> map = new LinkedHashMap<>();
			for (int n = 1; n <= 1000; n++) {
				String strn = Integer.toString(n);
				Character ans;
				if (n >= N && strn.compareTo(strN) >= 0)
					ans = 'Y';
				else if (n < N && strn.compareTo(strN) < 0)
					ans = 'Y';
				else
					ans = 'N';
				map.put(n, ans);
			}
			System.out.println(N + " " + map);
		}

	}

	static class ConsoleScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			try {
				while (!st.hasMoreElements())
					st = new StringTokenizer(br.readLine());
				return st.nextToken();
			} catch (IOException e) {
				throw new AssertionError(e);
			}
		}

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

}


Measured memory_bytes: 22948
using System;
using System.Linq;

namespace B___Guidebook
{
    class Program
    {
        static void Main (string[] args)
        {
            var n = int.Parse (Console.ReadLine ());
            var t = new Tuple<string, int, int>[n];
            for (var i = 0; i < n; i++)
            {
                var input = Console.ReadLine ().Split (' ');
                t[i] = Tuple.Create (input[0], int.Parse (input[1]), i + 1);
            }
            var quary = t.OrderBy (x => x.Item1).ThenByDescending (x => x.Item2);
            foreach (var p in quary)
            {
                Console.WriteLine (p.Item3);
            }
        }
    }
}

Measured memory_bytes: 13664
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define F first
#define S second
#define f(i,s,n) for(int i=(int)s;i<=(int)n;++i)
#define Fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=2e5+5;
vector< set<int> > adj(N);
vector<bool> vis(N,false);
int S=0;
void dfs(int s){
	vis[s]=1;
	for(auto  it:adj[s]){
		if(!vis[it]){
			++S;
			dfs(it);
		}
	}

}
void solve()
{
	int n,m;cin>>n>>m;
	f(i,1,m){
		int u,v;cin>>u>>v;
		adj[u].insert(v);
		adj[v].insert(u);
	}
	int mx=-1;
	f(i,1,n){
		dfs(i);
		mx=max(S,mx);
		S=0;
	}
	++mx;
	cout<<mx<<'\n';
}
int main()
{	Fast;
//	int t;cin>>t;
//	while(t--)
	solve();
}

Measured memory_bytes: 37380
k = int(input())
n = list(input())
for i in range(len(n)):
    if ord(n[i]) + k > 90:
        n[i] = chr((ord(n[i]) + k)- 90 + 64)
    else:
        n[i] = chr(ord(n[i]) + k)
print("".join(n))


Measured memory_bytes: 3060
class Integer
  def combination(k)
    self.factorial/(k.factorial*(self-k).factorial)
  end

  def factorial
    return 1 if self == 0
    (1..self).inject(:*)
  end
end

def upper_bound(arr, v)
  l = -1
  r = arr.size
  while l + 1 < r
    m = (l + r) / 2
    if arr[m] <= v then l = m
    else r = m
    end
  end
  r
end

EPS = 1e-9
n, m, l = gets.split.map(&:to_i)
p, t, v = n.times.map{ gets.split.map(&:to_i) }.transpose

time_set = n.times.map{ [0] * (m + 1) }
prob_set = n.times.map{ [0] * (m + 1) }
n.times do |i|
  s = v[i] == 0 ? Float::INFINITY : l / v[i].to_f
  (m + 1).times do |j|
    time_set[i][j] = s + t[i] * j
    prob_set[i][j] = ((p[i] / 100.0) ** j) * ((1 - p[i] / 100.0) ** (m - j)) * m.combination(j)
  end
end

prob_sum = prob_set.map{ |ps| ps.reverse.each_with_object([0]){ |p, arr| arr << arr[-1] + p }[1..-1].reverse }

n.times do |i|
  ret = 0
  (m + 1).times do |j|
    prob = prob_set[i][j]
    n.times do |k|
      next if i == k
      idx = upper_bound(time_set[k], time_set[i][j] + EPS)
      if idx == m + 1
        prob = 0
        break
      end
      prob *= prob_sum[k][idx]
    end
    ret += prob
  end
  puts '%.8f' % ret
end

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
#define endl            "\n"
#define ll                long long
#define all(v)            ((v).begin()), ((v).end())
#define sz(v)            ((int)((v).size()))
#define clr(v, d)        memset(v, d, sizeof(v))
#define rep(i, v)        for(int i=0;i<sz(v);++i)
#define lp(i, n)        for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)    for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)    for(int i=(j);i>=(int)(n);--i)
#define vi                vector <int>
#define vl                vector <ll>
#define ii                pair <ll,ll>
#define vii                vector <ii>
const double PI = 2 * acos(0.0);
void run() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
}
const ll M = 1e3, mod = 1e9 + 7;
int h, w;
char arr[M + 3][M + 3];
ll dp[M + 3][M + 3];
bool valid(int i, int j) {
	return i < h && j < w && arr[i][j] == '.';
}
ll sol(int i, int j) {
	//cout << i << ' ' << j << endl;
	if (!valid(i, j))
		return 0;
	if (i == h - 1 && j == w - 1)
		return 1;
	ll &ret = dp[i][j];
	if (~ret)
		return ret;
	return ret = (sol(i + 1, j) % mod + sol(i, j + 1) % mod) % mod;

}
int main() {
	run();
	cin >> h >> w;
	lp(i,h)
		lp(j,w)
			cin >> arr[i][j];

	clr(dp, -1);
	cout << sol(0, 0);
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
int R0,W0,C,R;
double calc(int X){return 1.0*(R0+X*R)/C-W0;}

int main(){
  while(1){
  cin>>R0>>W0>>C>>R;
  if(!R0&&!W0&&!C&&!R)break;
  int ans=0;
  while(calc(ans)<0)ans++;
  cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3080
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

public class Hello
{
    public static void Main()
    {
        int[] a = Console.ReadLine().Split(' ').Select(b => int.Parse(b)).ToArray();
        Console.WriteLine(((a[0] + a[1]) % 2 == 0) ? (a[0] + a[1]) / 2 : (a[0] + a[1]) /2 +1);
    }
}


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

int main() {
  int N, K, x;
  cin >> N >> K;
  int sum = 0 ;
    for (int i = 0; i < N; i++){
      cin >> x;
      if ( 2 * x <= K)
        sum += 2 * x;
      else 
    	sum += 2 * K - 2 * x;
    }
	cout << sum << endl;
}



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

int main(){
	int n,l=0;
  	cin >> n;
  	int k=1000;
  	vector<int> a(n); 
  	for (int i=0;i<n;i++){
    	cin >> a.at(i);
    }
  	for (int i=0;i<n;i++){
    	if (a.at(i)<=k) k=a.at(i);
      	if (a.at(i)>=l) l=a.at(i);
    }
  	cout << l-k << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

char s[1010];
int a[4];
int main(){
	scanf("%s",s);
	for(int i=0;s[i];i++){
		if(s[i]=='N')a[0]|=1;
		if(s[i]=='S')a[1]|=1;
		if(s[i]=='E')a[2]|=1;
		if(s[i]=='W')a[3]|=1;
	}
	puts((a[0]^a[1])||(a[2]^a[3])?"No":"Yes");
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main(){
	int N;
	cin>>N;
	string s[12345];
	int a[4]={0};
	int ans=0;
	for(int i=0;i<N;i++){
		cin>>s[i];
		int l=s[i].size();
		for(int j=1;j<l;j++){
			if(s[i][j-1]=='A'&&s[i][j]=='B'){
				ans++;
			}	
		}
		if(s[i][0]=='B'){
				a[0]++;
			}
			if(s[i][l-1]=='A'){
				a[1]++;
			}
			if(s[i][l-1]=='A'&&s[i][0]=='B'){
				a[2]++;
			}
	}
//	cout<<ans<<"  "<<a[0]<<"  "<<a[1]<<"  "<<a[2]<<endl;
	if(a[0]<a[1]){
		ans+=a[0];
	}
	else ans+=a[1];
	if(a[0]==a[1]&&a[0]==a[2]&&a[0]!=0) ans--;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <iterator>
#include <queue>
#include <cmath>
#include <cassert>

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

int vsum[2010][2010];
int hsum[2010][2010];

int H,W;
vector < string > S;

int main ()
{
    cin >> H >> W;
    S.resize(H);
    REP(i,H) cin >> S[i];

    for (int i = 0; i < H; i++) {
        int sumt = 0;
        int lm = 0;
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.') {
                sumt++;
                if (j == W - 1) {
                    for (int k = lm; k <= j; k++) {
                        hsum[i][k] = sumt;
                    }
                }
            } else if (S[i][j] == '#') {
                for (int k = lm; k < j; k++) {
                    hsum[i][k] = sumt;
                }
                sumt = 0;
                lm = j + 1;
            }
        }
    }

    for (int j = 0; j < W; j++) {
        int sumt = 0;
        int lm = 0;
        for (int i = 0; i < H; i++) {
            if (S[i][j] == '.') {
                sumt++;
                if (i == H - 1) {
                    for (int k = lm; k <= i; k++) {
                        vsum[k][j] = sumt;
                    }
                }
            } else if (S[i][j] == '#') {
                for (int k = lm; k < i; k++) {
                    vsum[k][j] = sumt;
                }
                sumt = 0;
                lm = i + 1;
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < H ; x++) {
        for (int y = 0; y < W; y++) {
            if (S[x][y] == '#') continue;
            ans = max(ans, vsum[x][y] + hsum[x][y] - 1);
        }
    }

    cout << ans << endl;

    return 0;
}








Measured memory_bytes: 35840
using System;
using System.Linq;

class Program{
	static void Main(){
    	var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
      	var count = 0;
      	while(input[0] > 0){
        	input[0] = input[0]- input[1];
            count++;
        }
      Console.Write(count);
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    string s, t;
    cin >> s >> t;

    ll ans = 0;
    for (ll i = 0; i < 3; i++)
    {
        if(s[i] == t[i])
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 764
#include<stdio.h>
int main(void){
int a[3],sum=0,max=0;
  for(int i=0;i<3;i++){
scanf("%d",&a[i]);
    if(a[i]>max)max=a[i];
    sum+=a[i];
  }
  printf("%d",sum-max);
  return 0;
}

Measured memory_bytes: 128
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 100100100100100;
ll gcd(ll a, ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}

int main() {
	ll a, b, x;
	cin >> a >> b >> x;
	if (a == 0)cout << b / x + 1 << endl;
	else {
		ll A = (a - 1) / x;
		ll B = b / x;
		cout << B - A << endl;
	}
}

Measured memory_bytes: 256
# 最小全域木（Kraskal法　＋　UnionFind）
class UnionFind:

    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        # print(self.rank)

    # 検索
    def findSet(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 根でないなら、親の要素で再走査
            # 走査する過程で親を書き換える(根を親につなぎなおす)
            self.par[x] = self.findSet(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.findSet(x)
        y = self.findSet(y)
        # 木の高さを比較し,高いほうに低いほうをくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方の木の高さを1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.findSet(x) == self.findSet(y)


# Kruskal法により最小全域木を求める
def compute_mst_kruskal(v, edges):
    # 重みの昇順で辺(edge)を並べ替える（あとで重みが最小のものから順番に走査するので）
    #重み(x[2])をkeyにしてソート
    edges = sorted(edges,key=lambda x: x[2])
    # | V |でUnionFind作成
    uf = UnionFind(v)
    mst = []

    # edgesが空になるまで繰り返す
    """
    for edge in edges:
        # ふたつの頂点が同じ木（集合）に属していないなら二つの木を連結する
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst
    """
    i = 0
    # 重みが小さい順に辺を走査していく
    while i < len(edges):
        # 最小の辺を選択
        edge = edges[i]

        """
        start : 選択された辺の始点
        end   : 選択された辺の終点
        無向グラフなのでstart,end自体に大きな意味はない
        """
        start = edges[i][0]
        end   = edges[i][1]

        # start,endが同じ木に属していなかったら
        if not uf.same_check(start, end):
            #print(edge)
            uf.union(start,end)
            mst.append(edge)
        i = i + 1
    return mst

def buble_sort(tdlist):
    i=0
    while i < len(tdlist)-1:
        if tdlist[i][2] > tdlist[i+1][2]:
            tmp = tdlist[i]
            tdlist[i] = tdlist[i+1]
            tdlist[i+1] = tmp
            i = -1
        i = i + 1

    #print(tdlist)
    return tdlist


def main():
    #print()
    p = []  ##appendのために宣言が必要
    v, e = map(int, input().split())
    # v：頂点数
    # e：辺
    # 入力受付
    i = 0
    while i < e:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;

    mst = compute_mst_kruskal(v, p)
    #print(sum(e.weight for e in mst))


    i = 0
    total_weight = 0
    while i < len(mst):
        total_weight = total_weight + mst[i][2]
        i = i + 1
    print(total_weight)



if __name__ == '__main__':
    main()


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

int main(){
    int n, amax = 0;
    cin >> n;
    vector<int> cnt(n,0);
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        cnt[a]++;
        amax = max(amax, a);
    }
    for(int i=0;i<=amax;i++){
        cnt[max(i,amax-i)]--;
    }
    bool ok = true;
    if(amax == 1) ok &= n == 2;
    for(int i=1;i<=amax;i++){
        if(i <= (amax+1)/2){
            ok &= cnt[i] == 0;
        }
        else{
            ok &= cnt[i] >= 0;
        }
    }
    cout << (ok ? "Possible" : "Impossible") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long

using namespace std;

typedef pair<int, int> td;

int op[1010][1010];

int main(){
    #ifdef ZERBRA
        freopen("code.inp", "r", stdin);
        //freopen("code.out", "w", stdout);
    #endif // ONLINE_JUDGE
    int n, m;
    scanf("%d%d\n", &n, &m);
    op[1][1] = 1;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            char c;
            scanf("%c", &c);
            if ((i > 1 || j > 1) && c == '.') op[i][j] = (op[i][j-1] + op[i-1][j]) % ((int)1e9+7);
        }
        scanf("\n");
    }
    printf("%d", op[n][m]);
    return 0;
}


Measured memory_bytes: 4224
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <string>

int testcase_ends() {
  size_t n;
  scanf("%zu", &n);
  if (n == 0) return 1;

  std::vector<std::string> s;
  scanf(" ");
  for (size_t i = 0; i < n; ++i) {
    char buf[1024+1];
    fgets(buf, sizeof buf, stdin);
    std::string line = buf;
    line.back() = ' ';
    std::string cur;
    for (size_t j = 0; j < line.length(); ++j) {
      if (line[j] == ' ') {
        s.push_back(cur);
        cur = "";
      } else {
        cur += line[j];
      }
    }
  }

  char top;
  scanf(" %c", &top);

  std::map<std::string, int> map;
  for (auto const& si: s)
    if (si[0] == top) ++map[si];

  std::vector<std::pair<int, std::string>> v;
  for (auto const& p: map) {
    v.emplace_back(-p.second, p.first);
  }
  std::sort(v.begin(), v.end());
  if (v.empty())
    return puts("NA"), 0;

  if (v.size() > 5) v.resize(5);
  for (size_t i = 0; i < v.size(); ++i)
    printf("%s%c", v[i].second.c_str(), i+1<v.size()? ' ':'\n');

  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2952
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    final int N=sc.nextInt();
    int[] n=new int[N];
    for(int i=0;i<N;i++){
      n[i]=sc.nextInt();
    }
    Arrays.sort(n);
    n[N-1]/=2;
    int sum=0;
    for(int i:n){
      sum+=i;
    }
    System.out.println(sum);
  }
}

Measured memory_bytes: 22740