akhauriyash/Code-Regression huggingface dataset:
import sys

input=sys.stdin.readline

L,N=map(int,input().split())
X=[int(input()) for i in range(N)]

accu1=[X[i] for i in range(N)]
accu2=[X[i] for i in range(N)]
for i in range(1,N):
    accu1[i]+=accu1[i-1]
for i in range(N-2,-1,-1):
    accu2[i]+=accu2[i+1]

ans=max(L-X[0],X[-1])
for i in range(1,N):
    j=N-i
    test=0
    if i<j:
        test1=2*accu1[i-1]-X[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])
        test2=2*accu1[i-1]+2*(i+1)*L-2*(accu1[2*i]-accu1[i-1])-(L-X[i])
        ans=max(test1,test2,ans)
        #print(test1,test2)
        #print(test1,test2)
    elif j<i:
        test1=2*L*j-2*accu2[-j]-(L-X[-j])+2*(accu2[-2*j]-accu2[-j])
        test2=2*L*j-2*accu2[-j]+2*(accu2[-2*j-1]-accu2[-j])-X[-j-1]
        #test2=2*sum(L-X[-k-1] for k in range(j))+2*sum(X[-k-1] for k in range(j,2*j+1))
        ans=max(test1,test2,ans)
        #print(test1,test2)
        #print(test1,test2)
    else:
        test1=2*accu1[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])-min(X[i-1],L-X[i])
        #test1=2*sum(X[k] for k in range(i))+2*sum(L-X[k] for k in range(i,2*i))-min(X[i-1],L-X[i])
        ans=max(ans,test1)

print(ans)


Measured memory_bytes: 105732
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
typedef long long ll;



int main() {
    int X; cin >> X;
    if(X==1){
        cout << 1 << endl;
        return 0;
    }
    int mx = 1;
    for(int i=2; i<=(int)sqrt(X); i++){
        int s = i*i;
        while(s<=X) s *= i;
        s /= i;
        mx = max(mx, s);
    }
    
    cout << mx << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n; cin>>n;
    vector<int> x(n);
    rep(i,n) cin>>x[i];

    ll ret = LINF;
    rep(i,101) {
        ll ans = 0;
        ll p = i;
        rep(j,n) {
            ll tmp = (x[j]-p);
            tmp *= tmp;
            ans += tmp;
        }
        chmin(ret,ans);
    }
    cout << ret << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>

int main(void){
	int i , a , buf , b , w , n , lines[31];
	scanf("%d" , &w);
	scanf("%d" , &n);
	for(i=1;i<=w;i++){
		lines[i] = i;
	}
	for(i=1;i<=n;i++){
		scanf("%d,%d" , &a , &b);
		buf = lines[a];
		lines[a] = lines[b];
		lines[b] = buf;
	}
	for(i=1;i<=w;i++){
		printf("%d\n" , lines[i]);
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>

using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define DEC(i, s) for (int i = (s); i >= 0; i--)

#define SIZE(v) (int)((v).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())

int n, r;
int seq[100][100];

int main() {
  while (cin >> n >> r, n|r) {
    REP(i, n) { seq[0][i] = n - i; }
    REP(i, r) {
      int p, c;
      cin >> p >> c;
      p--;
      int index = 0;
      REP(j, c) {
        seq[i + 1][index++] = seq[i][j + p];
      }
      REP(j, n) {
        if (j >= p && j < p + c) { continue; }
        seq[i + 1][index++] = seq[i][j];
      }
    }
    printf("%d\n", seq[r][0]);
  }
}

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

double halfadjust(double x){
	int tmp = static_cast<int>(x*10000);
	double ans = static_cast<double>(tmp)/10000;
	tmp = tmp%10;
	if(tmp >= 5)
		ans += 0.001;
	return ans;
}

double a,b,c,d,e,f;

void solve(){
	double x = (c*e-b*f)/(a*e-b*d);
	double y = (c*d-a*f)/(b*d-a*e);
	cout << setprecision(3) << fixed << halfadjust(x) << ' ';
	cout << halfadjust(y) << std::endl;
	//cout << setprecision(6);
}

int main(){
	while(cin >> a && cin >> b && cin >> c && cin >> d && cin >> e && cin >> f){
		if((!a&&!b)||(!d&&!e))
			break;
		solve();
	}
	return 0;
}

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

int main() {
    string s;
    cin>>s;
    int k=s.size()-2;
    string ans=s[0]+to_string(k)+s[s.size()-1];
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream> 
using namespace std;
int main()
{
  int A,B;
  cin>>A>>B;
  if (A==1) A=14;
  if (B==1) B=14;
  if (A>B)
    cout<<"Alice";
  if (A<B)
    cout<<"Bob";
  if (A==B)
    cout<<"Draw";
  system("pause");
  return 0;
}

Measured memory_bytes: 504
n, c, k = list(map(int, input().split()))
tlist = [int(input()) for i in range(n)]
tlmt = None
onb = 0
bnum = 1
for t in sorted(tlist):
  if tlmt is None:
    tlmt = t + k
  if t <= tlmt and onb < c:
    onb += 1
  else:
    tlmt = t + k
    onb = 1
    bnum += 1

print(bnum)

Measured memory_bytes: 8376
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

char s[100111],t[5];
int n,a[100111];
LL dp[100111][3];
int main()
{
	get1(n);
	s[1]='+';
	for(int i=1;i<=n;i++)
	{
		if(i>1)
		{
			scanf("%s",t);
			s[i]=t[0];
		}
		get1(a[i]);
	}
	for(int i=0;i<100111;i++)for(int j=0;j<3;j++)dp[i][j]=-Linf;
	dp[1][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		{
			LL t=dp[i][j];if((s[i]=='+')^(j&1))t+=a[i];else t-=a[i];
			if(s[i]=='-')dp[i+1][j+1]=max(dp[i+1][j+1],t);
			for(int j2=0;j2<=j;j2++)dp[i+1][j2]=max(dp[i+1][j2],t);
//			printf("i= %d j= %d dp= %lld\n",i,j,dp[i][j]);
		}
	}
	printendl(dp[n+1][0]);
	return 0;
}

Measured memory_bytes: 3072
n=int(input())
h = list(map(int,input().split()))
ma=0
cnt=0
prev=h[0]
for i in range(1,n):
  if h[i]<=prev:
    cnt+=1
    prev = h[i]
  else:
    ma=max(ma,cnt)
    cnt=0
    prev=h[i]
ma=max(ma,cnt)
print(ma)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int a, b, q;
    cin >> a >> b >> q;
    vll s(a+2), t(b+2), x(q);
    rep(i, a) cin >> s[i+1];
    rep(i, b) cin >> t[i+1];
    rep(i, q) cin >> x[i];
    s[0] = -LINF;
    s[a+1] = LINF;
    t[0] = -LINF;
    t[b+1] = LINF;
    sort(all(s));
    sort(all(t));

    rep(i, q) {
        ll ans1 = 0;
        ll p = x[i];
        int ids = lower_bound(all(s), p) - s.begin();
        int idt = lower_bound(all(t), p) - t.begin();
        if (s[ids] < t[idt]) {
            ans1 += abs(p - s[ids]);
            p = s[ids];
            int idt2 = lower_bound(all(t), p) - t.begin();
            ans1 += min(abs(p - t[idt2]), abs(p - t[idt2-1]));
        }
        else {
            ans1 += abs(p - t[idt]);
            p = t[idt];
            int ids2 = lower_bound(all(s), p) - s.begin();
            ans1 += min(abs(p - s[ids2]), abs(p - s[ids2-1]));
        }

        ll ans2 = 0;
        p = x[i];
        if (s[ids-1] > t[idt-1]) {
            ans2 += abs(p - s[ids-1]);
            p = s[ids-1];
            int idt2 = lower_bound(all(t), p) - t.begin();
            ans2 += min(abs(p - t[idt2]), abs(p - t[idt2-1]));
        }
        else {
            ans2 += abs(p - t[idt-1]);
            p = t[idt-1];
            int ids2 = lower_bound(all(s), p) - s.begin();
            ans2 += min(abs(p - s[ids2]), abs(p - s[ids2-1]));
        }

        cout << min(ans1, ans2) << endl;
    }

    return 0;
}

Measured memory_bytes: 3712
# abc149_a.py
# https://atcoder.jp/contests/abc149/tasks/abc149_a

# A - Strings /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 100点

# 問題文
# 英小文字のみからなる 2つの文字列 S, T が与えられます。
# これらの文字列を T, Sの順に空白を空けずに連結し、できる文字列を出力してください。

# 制約
#     S, Tは英小文字のみからなる文字列
#     S, T の長さは 1 以上 100以下

# 入力
# 入力は以下の形式で標準入力から与えられる。
# S T

# 出力
# できる文字列を出力せよ。

# 入力例 1
# oder atc

# 出力例 1
# atcoder

# S=oder, T= atc のとき、T, Sの順に連結してできる文字列は atcoder です。

# 入力例 2
# humu humu

# 出力例 2
# humuhumu


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    S, T = list(lines[0].split())
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    result = T + S

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['oder atc']
        lines_export = ['atcoder']
    if pattern == 2:
        lines_input = ['humu humu']
        lines_export = ['humuhumu']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9052
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

void WaitKey(void)
{
	getchar();
}

int main() {

	int n=0;
	int i, j, l;
	int cnt = 0, ba = 0, human[11] = { 0 };
	

	while (true) {
		char c[100 + 1];// cout << "n = " << n << endl;// WaitKey();
		cin >> n;
		
		if (n == 0) { return  0; }

		cin >> c;

		for (i = 0; i < 100; i++) {

			if (c[i] == 'S') {

				ba += human[cnt] + 1;

				human[cnt] = 0;

			}

			else if (c[i] == 'L') {

				human[cnt] += ba + 1;
				ba = 0;

			}

			else if (c[i] == 'M') {
				human[cnt]++;

			}
			if (cnt >= n - 1) {
				cnt = 0;
			}
			else cnt++;
		}

		sort(human, human + n);
		//puts("QA");
		for (i = 0; i < n; i++) {

			cout << human[i] << " ";
			human[i] = 0;

		}

		cout << ba << endl;
		cnt = ba = 0;

	}
	return 0;
}


Measured memory_bytes: 3180
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

const llong mod = (1e9) + 7;
llong h, w;
char mp[1005][1005];
llong dp[1005][1005];

int main() {
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> mp[i][j];
        }
    }

    dp[0][1] = 1;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (mp[i][j] == '#') continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            dp[i][j] %= mod;
        }
    }

    cout << dp[h][w] << endl;

    return 0;
}


Measured memory_bytes: 9088
N, M = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

D = [0] * N
C = [1] * N
D[0] = 1

for x, y in xy:
  x -= 1
  y -= 1
  if D[x] == 1:
    D[y] = 1
  C[x] -= 1
  C[y] += 1
  if C[x] == 0:
    D[x] = 0

print(sum(D))

Measured memory_bytes: 91608
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Measured memory_bytes: 123580
#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
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 = 2e+9 + 10;
typedef pair<ll, ll> P;

int main() {
    cin>>N>>A>>B;
    ll last, ans = 0;
    cin>>last;
    rep(i, N - 1){
        cin>>K;
        ans += min(A * (K - last), B);
        last = K;
    }
    cout<<ans<<endl;
}

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

struct unionfind{
    vector<int> d;
    unionfind(int n=0) : d(n, -1){}
    int find(int x) {//根を返す関数
        if(d[x]<0) return x;
        return d[x]=find(d[x]);//d[x]にfind[d[x]]の値を代入してそれを返している．これにより根に全ての子を繋げられる．
    }
    bool unite(int x, int y){
        x=find(x);y=find(y);
        if(x == y) return false;
        if(d[x]>d[y]) swap(x, y);//-なので逆にしている
        d[x]+=d[y];//連結成分サイズを保持している
        d[y]=x;//yの根をxにしている
        return true;
    }
    bool same(int x, int y){return find(x)==find(y);}//同じかどうかを判定
    int size(int x){return -d[find(x)];}//連結成分の数を返す
};
 
int main(void){
    int n, m;
    cin>>n>>m;
    vector<int> v(n);
    rep(i, n) {
        int a;
        cin>>a;
        --a;
        v[i] = a;
    }
    unionfind uf(n);
    rep(i, m){
        int x, y;
        cin>>x>>y;
        --x;--y;
        uf.unite(x, y);
    }
    int ans = 0;
    rep(i, n){
        if(uf.same(i, v[i])) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int human = sc.nextInt();
		int playedgame = sc.nextInt();
		int[] points = new int[human];
		int[] tag = new int[playedgame];
		int missct = 0;
		
		for(int i=0;i<playedgame;i++) tag[i] = sc.nextInt();
		for(int target : tag){
			for(int i=0;i<human;i++){
				int vote = sc.nextInt();
				if(vote-1 == target-1) points[i]++;
				else missct++;
			}
			points[target-1] += missct;
			missct = 0;
		}
		
		for(int pt : points) System.out.println(pt);
	}

}

Measured memory_bytes: 38340
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main()
{
    long i,j,t,a,b,n,temp;
    t=1;
    // cin>>t;
    while(t--)
    {
       cin>>a>>b;
       if(abs(a-b)>1)cout<<"0";
       else
       {
           if(a==b)
           {
               temp=1;
               while(a>0)
               {
                   temp=(temp*a)%mod;
                   a--;
               }
               temp=(temp*temp)%mod;
               cout<<(temp*2)%mod;
           }
           else 
           {
               temp=min(a,b);
               long ans=1;
               while(temp>0)
               {
                   ans=(temp*ans)%mod;
                   temp--;
               }
               cout<<(((ans*ans)%mod)*max(a,b))%mod;
           }
           
       }
        
    }
}

Measured memory_bytes: 256
object Main {

  import scala.collection.mutable.ArrayBuffer

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val S, T = sc.nextLine()
    var IDX = Array.fill(26)(ArrayBuffer[Int]())

    var i = 0
    while (i < S.length) {
      IDX(S(i) - 'a').append(i)
      i += 1
    }

    def lowerBound(arr: IndexedSeq[Int], x: Int): Int = {
      def dfs(l: Int, r: Int): Int =
        if (r - l > 1) {
          val center = l + (r - l) / 2
          if (arr(center) <= x) dfs(center, r)
          else dfs(l, center)
        } else r
      dfs(-1, arr.length)
    }

    i = 0
    var round = 0
    var j = -1
    while (i < T.length) {
      val IDX_T = IDX(T(i) - 'a')
      var idxT = lowerBound(IDX_T, j)
      if (idxT == IDX_T.length) {
        if (j == -1) {
          println("-1")
          return
        }
        round += 1
        j = -1
      } else {
        j = IDX_T(idxT)
        i += 1
      }
    }
    println(round.toLong * S.length.toLong + (j.toLong + 1L))
  }

}

Measured memory_bytes: 40456
#include <bits/stdc++.h>
using namespace std;
int a[4];
int main(){
  string in;
  cin>>in;
  for(int i=0;i<4;i++)a[i]=in[i]-'0';
  for(int x=0;x<8;x++){
    int sum=a[0];
    string s;
    s+=(char)('0'+a[0]);
    for(int i=0;i<3;i++){
      if(x&(1<<i)){
        sum+=a[i+1];
        s+='+';
        s+=(char)('0'+a[i+1]);
      }else{
        sum-=a[i+1];
        s+='-';
        s+=(char)('0'+a[i+1]);
      }
    }
    if(sum==7)return cout<<s<<"=7"<<endl,0;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;

int main(){
    int n, m, k, s;
    ll p, q;
    cin >> n >> m >> k >> s >> p >> q;
    
    vector<int> v[n+1], z(n+1, 0);
    while(k-- > 0){
        int x; cin >> x;
        z[x] = 2;
        v[0].push_back(x);
    }

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    queue<pair<int,int>> que;
    if(s){
        for(int tmp : v[0]) for(int next : v[tmp]) que.push({next, 1});
    }
    while(!que.empty()){
        auto pa = que.front(); que.pop();
        int pos = pa.first, cost = pa.second;
        if(z[pos] == 1)  continue;
        if(z[pos] != 2) z[pos] = 1;
        for(int next : v[pos]){
            if(z[next] != 1 && cost != s)    que.push({next, cost+1});
        }
    }

    vector<ll> dist(n+1, (1ll<<60));

    priority_queue<pair<ll,int>> pq;
    pq.push({-0, 1});

    while(!pq.empty()){
        auto pa = pq.top(); pq.pop();
        ll cost = -pa.first; int pos = pa.second;
        if(dist[pos] <= cost)   continue;
        dist[pos] = cost;
        for(int next : v[pos]){
            if(z[next] == 2)    continue;
            ll tmpc = cost + (z[next] == 0 ? p : q);
            if(tmpc < dist[next])   pq.push({-tmpc, next});
        }
    }

    cout << dist[n] - (z[n] == 0 ? p : q) << endl;

    return 0;
}


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

#define rep(i,n) for(ll i=0;i<n;i++)
#define repm(i,m,n) for(ll i=m;i<n;i++)
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define YesNo(a) (a)?cout<<"Yes"<<endl:cout<<"No"<<endl
#define YESNO(a) (a)?cout<<"YES"<<endl:cout<<"NO"<<endl
#define INF (2e9)
#define PI (acos(-1))
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007

typedef long long ll;

int a[1000001];
int main(){
  int k; cin >> k;

  a[1] = 7 % k;

  repm(i,2,1000001){
    a[i] = (a[i-1]*10 + 7) % k; 
  }

  repm(i,1,1000001){
    if(a[i] == 0){
      cout << i << endl;
      return 0;
    }
  }

  cout << -1 << endl;
}

Measured memory_bytes: 7572
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define rs(a, b) ((a) >> (b))
#define ls(a, b) ((a) << (b))
#define gcd __gcd
#define lcm(a, b) ((a * b) / gcd(a, b))
#define pq priority_queue
#define um unordered_map
#define us unordered_set
#define lb lower_bound
#define ub upper_bound
#define F first
#define B begin()
#define E end()
#define ln length()
#define sz size()
#define S second
#define em empty()
#define nani(x) cerr << #x << " is " << x << endl;
#define ch(x) (x - 'a' + 1)
#define mp make_pair
#define pb push_back
#define loop(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define scan(x, n) loop(i, 0, n) cin >> x[i];
#define adde(g, u, v) g[u].pb(v), g[v].pb(u);
#define addew(g, u, v, w) g[u].pb({ v, w }), g[v].pb({ u, w });
#define print(x, n) loop(i, 0, n) cout << x[i] << " ";
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inf 1000000000
#define mod 1000000007

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef pair<long, long> pll;
typedef vector<ii> vii;
typedef vector<pll> vll;
typedef um<int, int> umii;
typedef um<char, int> umci;
typedef map<char, int> mci;
typedef map<int, int> mii;

int dp[100001];
int main()
{
    fast;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;
    int a[n];
    scan(a, n);

    for (int i = 1; i < n; i++) {
        dp[i] = inf;
        for (int j = 1; j <= min(i, k); j++) {
            dp[i] = min(dp[i], dp[i - j] + abs(a[i - j] - a[i]));
        }
    }
    cout << dp[n - 1];
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>]
#include <map>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;


int main(){
ll n;cin>>n;
ll x[n+1];
x[0]=2;x[1]=1;
for(ll i=2;i<=n;i++)x[i]=x[i-1]+x[i-2];

cout<<x[n];

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static int[] t = {0,1,2,3,5,7,8,9};
	
	static void f(int n){
		if(n>=8)f(n/8);
		System.out.print(t[n%8]);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			f(n);
			System.out.println();
		}
	}
}

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

char s[2][2001];
int dp[2002][2002][2], n[2];
int main() {
	scanf("%d%d%s%s", &n[0], &n[1], s[0], s[1]);
	int Max = 0;
	for (int i = n[0]; i >= 0; i--)for (int j = n[1]; j >= 0; j--)rep(t, 2)rep(k, 2) {
		int a = (k ? dp[i][j + 1][!t] : dp[i + 1][j][!t]), b = (k ? j : i);
		if (b == n[k] || a % 2 == t)continue;
		if (t != (s[k][b] == 'I' ? 0 : 1))dp[i][j][t] = max(dp[i][j][t], a + 1);
		if (dp[i][j][t] % 2)Max = max(Max, dp[i][j][t]);
	}
	printf("%d\n", Max);
}

Measured memory_bytes: 34508
#include<iostream>
#define dff 1e-10
using namespace std;
int main(){
  int n;
  cin >>n;
  while(n--){
    double p[4][2],x;
    for(int i=0; i<4; i++)
      cin >>p[i][0]>>p[i][1];
    for(int i=0; i<2; i++)
      for(int j=0; j<2; j++)
	p[i*2+1][j]-=p[i*2][j];
    x = p[1][0]*p[3][1]-p[1][1]*p[3][0];
    if(-dff < x && x < dff) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1224
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(){
	int a, b, n, r = 0;
	scanf("%d", &n);
	for(int i = 0;i<n;++i){
		scanf("%d %d", &a, &b);
		r += b-a+1;
	}
	printf("%d\n",r);
	return 0;
}


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

int main() {
  long long A,B,C,K;
  cin >>A>>B>>C>>K;
  if(A>=K){cout<<K<<endl;}
  else if(A<K){
    if(B>=K-A){cout<<A<<endl;}
    else{
      if(C>=K-A-B){cout<<A-K+A+B<<endl;}
      else{cout<<K-A-C<<endl;}
    }
  }

}

Measured memory_bytes: 3552
;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter O3 '(optimize (speed 3) (safety 0) (debug 0)))
  (defparameter O2 '(optimize (speed 3) (safety 1))))

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))


;; Hauptteil

(defun split-by-one-space (str dest-arr)
  (declare #.O3
           (simple-string str)
  	   ((simple-array unum (*)) dest-arr))
  (loop for idx from 0 below (length dest-arr)
     for pos1 = 0 then (1+ pos2)
     for pos2 = (position #\space str :start pos1 :test #'char=)
     do (setf (aref dest-arr idx)
	      (parse-integer str :start pos1 :end pos2))
     finally (return dest-arr)))

(deftype unum nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (declare #.O3)
  (let* ((n (read))
	 (cache (make-hash-table))
	 (arr (make-array n :element-type 'unum)))
    (split-by-one-space (read-line) arr)
    (loop for a across arr do
	 (multiple-value-bind (num p)
	     (gethash a cache)
	   (declare (unum num))
	   (if p
	       (setf (gethash a cache) (+ num 1))
	       (setf (gethash a cache) 1))))
    (print-line
     (let ((sum 0))
       (declare (unum sum))
       (maphash #'(lambda (a num)
		    (declare (unum a num))
		    (if (>= num a)
			(incf sum (- num a))
			(incf sum num)))
		cache)
       sum))
  ))

#-swank(main)


;; Für Test
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

(defun test ()
  (with-input-from-string (*standard-input* (delete #\return (get-clipbrd)))
    (main)))


;; Für Benchmark
(defparameter *file-path* *load-pathname*)
(defparameter *dir-path* (pathname (directory-namestring *file-path*)))
(defparameter *dat-path* (merge-pathnames "test.dat" *dir-path*))

#+swank
(defun gendat ()
  (with-open-file (out *dat-path*
		       :direction :output :if-exists :supersede)
    ))

(defun bench ()
  (let ((*standard-output* (make-broadcast-stream)))
    (with-open-file (*standard-input* *dat-path*)
      (time (main)))))


Measured memory_bytes: 33252
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>


using namespace std;


template <class ...Args>
void Input(Args &...args)
{
	(cin >> ... >> args);
}

template <class T>
void InputArray(std::size_t size, T &t)
{
	t.resize(size);
	for (auto &e : t) {
		cin >> e;
	}
}

template <class ...Args>
void InputArray(std::size_t size, Args &...args)
{
	(InputArray(size, args), ...);
}

template <class ...Args>
void InputVerticalArray(std::size_t size, Args &...args)
{
	(args.resize(size), ...);
	for (int i = 0; i < size; i++) {
		((cin >> args[i]), ...);
	}
}

template <class ...Args>
void Output(const Args &...args)
{
	((cout << args << ' '), ...) << endl;
}

template <class ...Args>
void OutputVertical(const Args &...args)
{
	((cout << args << endl), ...);
}

template <class T>
void OutputArray(const T &t)
{
	for (const auto &e : t) {
		cout << e << ' ';
	}
	cout << endl;
}

template <class ...Args>
void OutputArray(const Args &...args)
{
	(OutputArray(args), ...);
}

template <class ...Args>
void OutputVerticalArray(const Args &...args)
{
	for (int i = 0; i < min({ args.size()... }); i++) {
		((cout << args[i] << ' '), ...) << endl;
	}
}


#define inp(type, ...) \
	type __VA_ARGS__; \
	Input(__VA_ARGS__)

#define inpa(type, size, ...) \
	type __VA_ARGS__; \
	InputArray((size), __VA_ARGS__)

#define inpva(type, size, ...) \
	type __VA_ARGS__; \
	InputVerticalArray((size), __VA_ARGS__)

#define otp(...) \
	Output(__VA_ARGS__)

#define otpv(...) \
	OutputVertical(__VA_ARGS__)

#define otpa(...) \
	OutputArray(__VA_ARGS__)

#define otpva(...) \
	OutputVerticalArray(__VA_ARGS__)

#define rep(counter, range) \
	for (int (counter) = 0; (counter) < (range); (counter)++)

#define repi(range) \
	rep(i, range)

#define rrep(counter, range) \
	for (int (counter) = (range) - 1; (counter) >= 0; (counter)--)

#define rrepi(range) \
	rrep(i, range)

#define repc(element, container) \
	for (auto &(element) : (container))

#define repe(container) \
	repc(e, container)

#define all(container) \
	(container).begin(), (container).end()

#ifdef __CCR__
#	define dlog(x) clog << #x " = " << x << endl
#else
#	define dlog(x)
#endif



int main()
{
	inp(string, s, t);
	
	int cntmax = 0;
	int cnt;
	repi(s.size() - t.size() + 1) {
		cnt = 0;
		rep(j, t.size()) {
			if (s[i + j] == t[j]) cnt++;
		}
		if (cnt > cntmax) cntmax = cnt;
	}
	
	otp(t.size() - cntmax);
	
	return 0;
}


Measured memory_bytes: 3204
#include<iostream>

int main(){
    int n;  std::cin >> n;
    std::string str[n];
    int cnt[] = {0,0,0,0};
    const int AC_ = 0, WA_ = 1, TLE_ = 2, RE_ = 3;

    for(int i=0; i < n; i++){
        std::cin >> str[i];
    }

    for(int i=0; i < n; i++){
        if(str[i] == "AC"){
            cnt[AC_] += 1;
            continue;

        }
        else if(str[i] == "WA"){
            cnt[WA_] += 1;
            continue;

        }
        else if(str[i] == "TLE"){
            cnt[TLE_] += 1;
            continue;
        }
        else if(str[i] == "RE"){
            cnt[RE_] += 1;
            continue;
        }
            
    }

    

    std::cout << "AC x " << cnt[AC_] << std::endl;
    std::cout << "WA x " << cnt[WA_] << std::endl;
    std::cout << "TLE x " << cnt[TLE_] << std::endl;
    std::cout << "RE x " << cnt[RE_] << std::endl;
    
    return 0;
}

Measured memory_bytes: 6748
#include <bits/stdc++.h>
using namespace std;
//------------------------------------------------------------------//
typedef long long ll;
typedef vector<int> vi;
template <typename T> inline T read() {
	bool f = 1; T x = 0; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = !f;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return f ? x : -x;
}
#define gi read<int>()
#define gl read<ll>()
//------------------------------------------------------------------//

int n;
int main() {
	cin >> n;
	int price = (n / 1000) * 1000;
	while (price < n) price += 1000;
	cout << price - n << endl;
	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;

/////////////////////////////////////////////////////////////////////////////////////////////
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main()
{
    double n; cin >> n;
    cout << (double)2 * n * 3.141592 << endl;
    return 0;
}



Measured memory_bytes: 3784
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  string rocks;
  cin >> rocks;
  string goal;
  goal.reserve(goal.size());
  int r = 0;
  int w = 0;
  for (size_t i = 0; i < rocks.size(); ++i) {
    if (rocks[i] == 'R') {
      ++r;
    } else {
      ++w;
    }
  }
  for (size_t i = 0; i < r; ++i) {
    goal += "R";
  }
  for (size_t i = 0; i < w; ++i) {
    goal += "W";
  }

  int diff_r = 0;
  int diff_w = 0;
  for (size_t i = 0; i < goal.size(); ++i) {
    if (rocks[i] == 'R' && goal[i] == 'W') {
      ++diff_r;
    }
    if (rocks[i] == 'W' && goal[i] == 'R') {
      ++diff_w;
    }
  }
  cout << max(diff_r, diff_w) << endl;
  return 0;
}

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int main()
{
    ios::sync_with_stdio(false);

    vector<int> cap = {25, 50, 100, 200};
    vector<PII> tea(4);

    rep(i, 4) {
        cin >> tea[i].first;
        tea[i].second = cap[i];
    }

    ll N; cin >> N;
    N *= 100;

    sort(tea.begin(), tea.end());

    ll ans = INFLL;
    do {
        ll n = N;
        ll tmp = 0;
        for (auto t : tea) {
            if (n > 0 && n >= t.second) {
                ll num = n / t.second;
                tmp += num * t.first;
                n -= num * t.second;
            }
        }
        // assert(n == 0);
        if (n == 0) ans = min(tmp, ans);
    } while (next_permutation(tea.begin(), tea.end()));

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
int par[111111],ran[111111];
void init(int n){
	rep(i,n){
		par[i]=i;
		ran[i]=0;
	}
}
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unite(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return;
	if(ran[x]<ran[y])par[x]=y;
	else{
		par[y]=x;
		if(ran[x]==ran[y])ran[x]++;
	}
}
bool same(int x,int y){
	return find(x)==find(y);
}
int n,q,a,b,c;
signed main(){
	cin>>n>>q;
	init(n);
	while(q--){
		cin>>a>>b>>c;
		if(a)cout<<same(b,c)<<endl;
		else unite(b,c);
	}
	return 0;
}



Measured memory_bytes: 3248
import fractions
N,M=map(int,input().split())
S=input()
T=input()
g=fractions.gcd(N,M);l=N*M//g
if(g==1):
    print(l if S[0]==T[0] else -1)
    exit()
n=N//g;m=M//g
for i in range(g):
    if(S[n*i]!=T[m*i]):
        print(-1)
        exit()
print(l)

Measured memory_bytes: 5428
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);

int N;
int a[100000];
int main() {
	cin >> N;
	rep(i, N) cin >> a[i];

	vint vec;
	rep(i, N){
		if(i == 0) vec.push_back(a[i]);
		else{
			if(a[i] > vec[vec.size()-1]) vec.push_back(a[i]);
			vint::iterator it = lower_bound(vec.begin(), vec.end(), a[i]);
			*it = a[i];
		}
	}
	cout << vec.size() << endl;
}

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

ans = 0
flag = True
while flag:
    for i in range(n):
        if a[i] % 2 == 1:
            flag = False
            break
        else:
            a[i] /= 2
    ans += 1
print(ans-1)


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

const long long MAX = 10000000;  // TLEならば小さくする
const long long MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (long long i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(long long n, long long k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// 重複組み合わせ計算
// n 種類のものから重複を許して r 個選ぶ場合の数
// r 個のものを n グループに(0個を許して)割り当てる場合の数
// n - 1 個の仕切りと r 個の玉を一列に並べる場合の数
long long H(long long n, long long r) {
	return COM(n + r - 1, r);
}

int main() {
	
	ll n, k; cin >> n >> k;
	ll red = n - k;
	COMinit(); // 前処理
	for (ll i = 1; i <= k; i++) {
		ll x = COM(k - 1, k - i);
		ll y = COM(red + 1, red - i + 1);
		ll ans = x * y;
		ans %= MOD;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 237924
#include <queue>
#include <limits>
#include <vector>
#include <iostream>
using namespace std;
struct edge {
	int to, cost, w;
	edge() : to(0), cost(0), w(0) {};
	edge(int to_, int cost_, int w_ = 0) : to(to_), cost(cost_), w(w_) {};
};
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
template<class Type>
std::vector<Type> shortest_path_dijkstra(std::vector<std::vector<edge> > &G, int s) {
	std::priority_queue<edge> que; que.push(edge(s, 0));
	std::vector<Type> ret(G.size(), std::numeric_limits<Type>::max()); ret[s] = 0;
	while (!que.empty()) {
		edge u = que.top(); que.pop();
		for (edge e : G[u.to]) {
			if (ret[e.to] > ret[u.to] + e.cost) {
				ret[e.to] = ret[u.to] + e.cost;
				que.push(edge(e.to, -ret[e.to]));
			}
		}
	}
	return ret;
}
int N, M, p, q, r, s;
int main() {
	while (cin >> N >> M, N) {
		vector<vector<edge> > G(N);
		for (int i = 0; i < M; i++) {
			cin >> p >> q >> r >> s; p--, q--;
			G[p].push_back(edge(q, r, s));
			G[q].push_back(edge(p, r, s));
		}
		vector<int> dist = shortest_path_dijkstra<int>(G, 0);
		vector<int> ret(N, 1999999999);
		for (int i = 0; i < N; i++) {
			for (edge e : G[i]) {
				if (dist[e.to] - dist[i] == e.cost) {
					ret[e.to] = min(ret[e.to], e.w);
				}
			}
		}
		int sum = 0;
		for (int i = 1; i < N; i++) sum += ret[i];
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 4140
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		if (IsTolk(input.split("")) && IsTolk(input.substring(0, ((input.length() - 1) / 2)).split(""))
				&& IsTolk(input.substring(((input.length() + 3) / 2) - 1).split(""))) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

	private static boolean IsTolk(String[] split) {
		boolean res = true;
		for (int i = 0; i < split.length / 2; i++) {
			if (!(split[i].equals(split[split.length - i - 1]))) {
				res = false;
				break;
			}
		}
		return res;
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Welcome to my source code!

vector<int> nxt[10];
ll k;
ll cnt;
string ans;

bool dfs(int dgt, int cur, string s) {
    if (cur == dgt) {
        cnt++;
        if (cnt == k) {
            ans = s;
            return true;
        }
        return false;
    }
    ll t = stoi(s);
    t %= 10;
    for (int i = max(0LL, t - 1); i <= min(9LL, t + 1); i++) {
        dfs(dgt, cur + 1, s + to_string(i));
    }
}

int main() {
    nxt[0].push_back(0); nxt[0].push_back(1);
    nxt[1].push_back(0); nxt[1].push_back(1); nxt[1].push_back(2);
    nxt[2].push_back(1); nxt[2].push_back(2); nxt[2].push_back(3);
    nxt[3].push_back(2); nxt[3].push_back(3); nxt[3].push_back(4);
    nxt[4].push_back(3); nxt[2].push_back(4); nxt[2].push_back(5);
    nxt[5].push_back(4); nxt[2].push_back(5); nxt[2].push_back(6);
    nxt[6].push_back(5); nxt[2].push_back(6); nxt[2].push_back(7);
    nxt[7].push_back(6); nxt[2].push_back(7); nxt[2].push_back(8);
    nxt[8].push_back(7); nxt[8].push_back(8); nxt[8].push_back(9);
    nxt[9].push_back(8); nxt[9].push_back(9);
    cin >> k;
    for (int dgt = 1; dgt <= 10; dgt++) {
        for (int i = 1; i <= 9; i++) {
            dfs(dgt, 1, to_string(i));
        }
    }
    cout << ans << endl;
}

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

int conv(int a,int b){
    int c=1;
    int d=1;
    for(int i=0;i<b;i++){
        c *= a-i;
        d *= b-i;
    }
    return c/d;
}

int main(){
    int n,m;
    cin >> n >>m;
    cout << conv(n,2) + conv(m,2) <<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
using namespace std;
#define X 10000000
int main() {
	int n, m; while (cin >> n >> m&&n&&m) {
		vector<int>taro, hanako;
		int num;
		for (int i = 0; i < n; i++) {
			cin >> num; taro.push_back(num);
		}
		for (int i = 0; i < m; i++) {
			cin >> num; hanako.push_back(num);
		}
		sort(taro.begin(), taro.end());
		sort(hanako.begin(), hanako.end());
		int sum1 = accumulate(taro.begin(), taro.end(), 0);
		int sum2 = accumulate(hanako.begin(), hanako.end(), 0);
		int sa = (sum1 - sum2);
		if (abs(sa) % 2 == 1) { cout << -1 << endl; continue; }
		sa /= 2;
		int f = 0;
		for (int i = 0; i < n; i++) {
			if (f)break;
			for (int j = 0; j < m; j++) {
				if (taro[i] - hanako[j] == sa) {
					cout << taro[i] << " " << hanako[j] << endl;
					goto loop_end;
				}
			}
		}
		cout << -1 << endl;
	loop_end:;
	}
	return 0;
}

Measured memory_bytes: 3044
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static boolean solve() {
		int n = in.nextInt();
		if (n == 0) return false;

		Dice d = new Dice();
		int sum = 1;
		for (int i=0; i<n; i++) {
			String s = in.next();
			if ("North".equals(s)) {
				d.rotate(1);
			} else if ("East".equals(s)) {
				d.rotate(0);
			} else if ("West".equals(s)) {
				d.rotate(2);
			} else if ("South".equals(s)) {
				d.rotate(3);
			} else if ("Right".equals(s)) {
				d.rotate(4);
			} else if ("Left".equals(s)) {
				d.rotate(5);
			}

			sum += d.face[Dice.TOP];
		}
		out.println(sum);

		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		dump((end-start) + "ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

class Dice implements Cloneable{

	public static final int TOP = 0;
	public static final int BOTTOM = 1;
	public static final int FRONT = 2;
	public static final int BACK = 3;
	public static final int LEFT = 4;
	public static final int RIGHT = 5;

	public static final int[][] roll = {
		{TOP,LEFT,BOTTOM,RIGHT},//+x
		{TOP,FRONT,BOTTOM,BACK},//+y
		{TOP,RIGHT,BOTTOM,LEFT},//-x
		{TOP,BACK,BOTTOM,FRONT},//-y

		{FRONT,RIGHT,BACK,LEFT},//cw
		{FRONT,LEFT,BACK,RIGHT},//ccw
	};

	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};

	final int[] face;

	public Dice() {
		this.face = new int[6];
		this.face[TOP] = 1; this.face[BOTTOM] = 6; this.face[FRONT] = 2;
		this.face[BACK] = 5; this.face[LEFT] = 4; this.face[RIGHT] = 3;
	}
	public Dice(int[] nums) {
		this.face = nums.clone();
	}

	public void rotate(int dir) {
		int temp = face[roll[dir][0]];
		for (int i=0; i<3; i++) {
			face[roll[dir][i]] = face[roll[dir][i+1]];
		}
		face[roll[dir][3]] = temp;
	}

	static void swap(Dice d1, Dice d2) {
		for (int i=0; i<6; i++) {
			int temp = d1.face[i];
			d1.face[i] = d2.face[i];
			d2.face[i] = temp;
		}
	}

	public boolean equals(Dice d) {
		return  this.face[TOP] == d.face[TOP] && this.face[BOTTOM] == d.face[BOTTOM]
			&& this.face[FRONT] == d.face[FRONT] && this.face[BACK] == d.face[BACK]
			&& this.face[LEFT] == d.face[LEFT] && this.face[RIGHT] == d.face[RIGHT];
	}

	public String toString() {
		return Arrays.toString(face);
	}

	@Override
	public Dice clone() {
		return new Dice(this.face);
	}
}

Measured memory_bytes: 33620
import java.util.Scanner;
import java.util.Arrays;

public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		StringBuffer str = new StringBuffer(sc.next());
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){
			String row = sc.next();
			int a = sc.nextInt();
			int b = sc.nextInt() + 1;
			switch(row){
				case "print":
					System.out.println(str.substring(a, b));
					break;
				case "reverse":
					StringBuffer reverse = new StringBuffer(str.substring(a, b));
					str = str.replace(a, b, reverse.reverse().toString());
					break;
				case "replace":
					str = str.replace(a, b, sc.next());
					break;
				default:
			}
		}
	}
}



Measured memory_bytes: 28772
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>
using namespace std;

static const int MAX = 100000;

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;
int indeg[MAX];

void bfs(int s){
    queue<int> q;
    q.push(s);
    V[s] = true;
    while(!q.empty()){
        int u = q.front(); q.pop();
        out.push_back(u);
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i];
            indeg[v]--;
            if(indeg[v]==0 && !V[v]){
                V[v] = true;
                q.push(v);
            }
        }
    }
}

void tsort(){
    for(int i=0; i<N; i++){
        indeg[i] = 0;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<G[i].size(); j++){
            int v = G[i][j];
            indeg[v]++;
        }
    }
    for(int u=0; u<N; u++){
        if(indeg[u]==0 && !V[u]) bfs(u);
    }
    for(list<int>::iterator it=out.begin(); it!=out.end(); it++){
        cout << *it << endl;
    }
}

int main(){
    int s,t,M;
    
    cin >> N >> M;
    for(int i=0; i<N; i++) V[i] = false;
    for(int i=0; i<M; i++){
        cin >> s >> t;
        G[s].push_back(t);
    }
    
    tsort();
}

Measured memory_bytes: 6236