akhauriyash/Code-Regression huggingface dataset:
def main():
    # 行先、上限、逆辺
    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        flow = 0
        while True:
            used = [False]*n
            used2 = [0]*n
            q = [(s, 10**6)]
            ans = [0]
            while q:
                v, f = q[-1]
                a = ans[0]
                if a == 0:
                    if v == t:
                        ans[0] = f
                        continue
                    gkv, gv = gkey[v], g[v]
                    l, used[v] = len(gkv), True
                    while True:
                        i = used2[v]
                        used2[v] += 1
                        if i < l:
                            to = gkv[i]
                            cap, to2 = gv[to], [to, -to-1][to < 0]
                            if (not used[to2]) and cap:
                                q.append((to2, min(f, cap)))
                                break
                        else:
                            q.pop()
                            ans[0] = 0
                            break
                else:
                    q.pop()
                    if q:
                        v = q[-1][0]
                        i = used2[v]-1
                        to = gkey[v][i]
                        g[v][to] -= a
                        g[[to, -to-1][to < 0]][-v-1] += a
            if not ans[0]:
                return flow
            flow += ans[0]

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()


Measured memory_bytes: 47708
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main(){
    int max = 1000000;
    vector<int> prime(max, 1);
    //ツエツδ可トツスツテツネツスツづ個づ督づゥツつ「
    
    for(int i = 0; i < max; i++){
        prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    for(int i = 2; i <= max; i++){
        if(prime[i] == 1){
            for(int j=i+i; j <= max; j+=i){
                prime[j] = 0;
            }        
        }
    }
    int n;
    while(cin >> n){
        int ans = 0;
        for(int i=0; i <= n; i++){
            if(prime[i] == 1){
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

const int MAX_N=1e6;

int prime[MAX_N];
bool is_prime[MAX_N+1];

int sieve(int n){
    int p=0;
    for (int i=0;i<=n;i++) is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for (int i=2;i<=n;i++){
        if (is_prime[i]){
            prime[p++]=i;
            for (int j=2*i;j<=n;j+=i) is_prime[j]=false;
        }
    }
    return p;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    sieve(1e6);
    while(true){
        if (is_prime[n]) break;
        else ++n;
    }
    cout << n << endl;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MOD = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination MOD prime
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} c(10000007);
// c(5, 2) → 10, c.p(5, 2) → 20, c.fact[4] → 24

mint F(int x, int y) {
  return c(x+y+2, x+1);
}

int main() {
  // 4隅に注目、各点の右上のnCr-1
  // -1の部分は無視、制約は全て1以上
  int R1, C1, R2, C2;
  cin >> R1 >> C1 >> R2 >> C2;
  mint ans = (F(R2, C2) - F(R2, C1-1) - F(R1-1, C2) + F(R1-1, C1-1));
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 159332
#include<bits/stdc++.h>
using namespace std ;
using ll = long long ;
int main(){
	int n,k ;
	cin >> n ;
	ll dp[n][n];
	ll a[n] ;
	for(auto i=0;i<n;i++)
		cin >> a[i] ;
	for(int i=n-1; i>= 0 ; i--){
		for(int j=i; j<n ; j++){
			if(i==j)
				dp[i][j] = a[i] ;
			else
				dp[i][j] = 	max(a[i]-dp[i+1][j], a[j]-dp[i][j-1]) ;
		}
	}
	cout << dp[0][n-1] << endl ;
}




Measured memory_bytes: 70144
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
t, x = M()
print(t/x)

Measured memory_bytes: 3888
N = int(input())

flag = True

bw = ''
wl = []
for i in range(N):
    w = input().strip()
    if i != 0:
        if bw[-1] is not w[0]:
            flag = False
        if w in wl:
            flag = False
        if flag is False:
            break
    wl.append(w)
    bw = w

if flag:
    print('Yes')
else:
    print('No')

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

using namespace std;

typedef long long ll;

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

        int n, s = 0, a = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
                int x;
                cin >> x;
                a += s * x;
                s += x;
        }
        cout << a << "\n";

        return 0;
}


Measured memory_bytes: 256
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

string s;

void solve() {
    int c_n = 0, c_w = 0, c_s = 0, c_e = 0;
    rep(i, s.length()) {
        if (s[i] == 'N') c_n++;
        else if (s[i] == 'W') c_w++;
        else if (s[i] == 'S') c_s++;
        else if (s[i] == 'E') c_e++;
    }
    if ((c_n == 0 && c_s != 0) || (c_n != 0 && c_s == 0) ||
        (c_w == 0 && c_e != 0) || (c_w != 0 && c_e == 0)) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

int main() {
    cin >> s;
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int d,x;
	int sum=0;
	while(scanf("%d",&d)!=EOF){
		sum=0;
		for(x=d;x<600;x+=d){
			sum+=x*x*d;
		}
		printf("%d\n",sum);
	}
	
	return 0;
}

Measured memory_bytes: 596
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

lis = [0]*N
ans = 0
for key, v in Counter(A).items():
	lis[key-1] = v
	ans += v*(v-1)//2

for i in range(N):
	print(ans-lis[A[i]-1]+1)


Measured memory_bytes: 27196
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <string>
#include <sstream>
int fix()
{
    //example to format floating point numbers.
    double pi = 3.141592653589793;
    double r = 3.141592653589793 * 128;
    std::ios_base::fmtflags f(std::cout.flags()); //[1]
    std::cout << "default:\n  " << pi << " " << r << "\n";
    std::cout << std::setprecision(4) << "setprecision(4):\n  " //[2]
              << pi << " " << r << "\n";
    std::cout << std::setiosflags(std::ios::fixed) << "setiosflags(std::ios::fixed):\n  " //[2]
              << pi << " " << r << "\n";
    std::cout << std::setprecision(5) << "setprecision(5):\n  " //[2]
              << pi << " " << r << "\n";
    std::cout.flags(f);
    std::cout << "reset:\n  " << pi << " " << r << "\n";
    //[1] https://stackoverflow.com/questions/2273330/restore-the-state-of-stdcout-after-manipulating-it
    //[2] https://stackoverflow.com/questions/4217510/how-to-cout-the-correct-number-of-decimal-places-of-a-double-value
    return 0;
}
void multipleLines()
{
    //example to parse multiple lines input.
    std::istringstream isin("1 2 3\n3 2 4\n0 0 0");

    for (std::string str; std::getline(isin, str);)
    {
        std::istringstream tisin(str);
        int a, b, c;
        tisin >> a >> b >> c;
        std::cout << a << " " << b << " " << c << "\n";
    }
    //[1]  https://stackoverflow.com/questions/19767644/c-parsing-input-string-to-variables
}
#include <vector>
#include <set>
#include <map>

int main()
{
    int n;
    std::vector<int> vv(4 * 30);
    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        int b, f, r, v;
        std::cin >> b >> f >> r >> v;
        b--;
        f--;
        r--;
        vv[b * 30 + f * 10 + r] += v;
    }

    for (int b = 0; b < 4; b++)
    {
        for (int f = 0; f < 3; f++)
        {
            for (int r = 0; r < 10; r++)
            {
                std::cout << " " << vv[b * 30 + f * 10 + r];
            }
            std::cout << "\n";
        }
        if (b != 3)
        {
            std::cout << "####################\n";
        }
    }
    return 0;
}


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

#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)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;
///////////////////////////////////////////////
// for template
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
/// 🍈( '-' 🍈 |AC|
int main() {
    string S,T;
    cin >> S >> T;
    int ans = 0;
    REP(i,S.length()){
        if (S[i] != T[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3908
#include<stdio.h>
void swap(int *a,int *b){
  int r;
  r=*a;
  *a=*b;
  *b=r;
}
void b(int *f){
  int i,j;
  for(i=7;i>0;i--){
    for(j=0;j<i;j++){
      if(f[j]>f[j+1])swap(&f[j],&f[j+1]);
    }
  }
}
void d(int *f){
  int i,j;
  for(i=7;i>0;i--){
    for(j=0;j<i;j++){
      if(f[j]<f[j+1])swap(&f[j],&f[j+1]);
    }
  }
}
int main(){
  int da,ba,i,j,k,a,l;
  char g;
  int f[8];
  scanf("%d",&a);
  for(i=0;i<a;i++){
    for(j=0;j<8;j++){
      scanf(" %c",&g);
      f[j]=g-'0';
    }
    b(f);
    ba=0;
    for(j=0;j<8;j++){
      l=1;
      for(k=0;k<j;k++)l=l*10;
      ba+=f[j]*l;
    }
    d(f);
    da=0;
    for(j=0;j<8;j++){
      l=1;
      for(k=0;k<j;k++)l=l*10;
      da+=f[j]*l;
    }
    printf("%d\n",ba-da);
  }
  return 0;
}


Measured memory_bytes: 596
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<pair<ll,ll> > > vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) x.begin() , x.end()
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define left (node << 1)
#define right (node << 1) + 1
#define pii pair<int,int> 
#define mii map<int,int>
#define vi vector<int>
#define umii unordered_map<int,int>
#define mod 998244353
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<": " <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl

#define repo(i,o,e) for(int i = o ; i < e ; i++)
#define rep(n) for(int i = 0 ; i < n ; i++)
const ll sz = 2e5+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve(){
    int a,b;
    cin >> a >> b;
    if(a > 12){
        cout << b << endl;
    }
    else if(a > 5 && a < 13){
        cout << b/2 << endl;
    }
    else if(a < 6 && a > -1){
        cout << 0 << endl;
    }
}

int main(){
    FIO;
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
import sys
import os

def file_input():
    f = open('CODE_FESTIVAL_2017Final/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    S=input()

    a=b=c=0

    for s in S:
        if s=='a':
            a+=1
        elif s=='b':
            b+=1
        else:
            c+=1

    if max(a,b,c)-min(a,b,c)<=1:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()


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

int main(){
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  char C1 = s1[0] - 32;
  char C2 = s2[0] - 32;
  char C3 = s3[0] - 32;
  cout << C1 << C2 << C3;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;int f=1;char c=getchar();
	for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T> inline void print(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
#define re register
const int mod=1e9+7;
int x[100005],n;
int mul(int a,int b)
{
	return 1LL*a*b%mod;
}
int main()
{
	read(n);
	for(re int i=1;i<=n;++i) read(x[i]);
	int pre=0,cnt=0,ans=1;
	for(re int i=1;i<=n;++i)
		if(x[i]>pre) cnt++,pre+=2;
		else ans=mul(ans,cnt+1);
	for(re int i=1;i<=cnt;++i) ans=mul(ans,i);
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    long long x, k, d;

    cin >> x >> k >> d;

    long long ans = -1;
    x = abs(x);
    long long wtime;
    wtime = x / d;

    if (wtime >= k) {
        ans = x - d * k;
    }
    else if (wtime < k) {
        if (wtime % 2 == 0) {
            if (k % 2 == 0) {
                ans = x - d * wtime;
            }
            else if (k % 2 == 1) {
                ans = x - d * (wtime + 1);
            }
        }
        else if (wtime % 2 == 1) {
            if (k % 2 == 0) {
                ans = x - d * (wtime + 1);
            }
            else if (k % 2 == 1) {
                ans = x - d * wtime;
            }
        }
    }
    cout << abs(ans);
}

Measured memory_bytes: 3192
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 1 << 10


int n;

int main(){
    cin >> n;
    std::vector<int> a(n+2);
    std::vector<int> left(n+3);
    std::vector<int> right(n+3);
    for(int i=1; i<n+1; ++i){
        cin >> a[i];
    }
    a[0] = 0;
    a[n+1] = 0;
    left[0] = 0; left[n+2]=0;
    right[0] = 0; right[n+2]=0;
    for(int i=1; i<n+2; i++){
        left[i]=left[i-1]+abs(a[i]-a[i-1]);
    }

    for(int i=n+1; i>=1; --i){
        right[i]=right[i+1]+abs(a[i]-a[i-1]);
    }


    for(int i=1; i<=n; i++){
        cout << left[i-1] + abs(a[i+1]-a[i-1]) + right[i+2] << endl;
    }





    return 0;

}


Measured memory_bytes: 2432
#include <stdio.h>

int main()
{
  int n;
  scanf("%d",&n);
  
  int i;
  int cnt=0,ans=0;
  for(i=0;i<n;i++)
  {
    int a;
    scanf("%d",&a);
    if(a>=cnt){
      ans++;
      cnt=a;
    }
  }
  
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,z[200];
    cin>>n;
    string a[200];
    for(int i=0;i<n;i++){
        cin>>a[i];
        z[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]==a[j]) z[j]++;
        }
    }
    cin>>m;
    for(int i=n;i<m+n;i++){
        cin>>a[i];
        z[i]=-1;
        for(int j=0;j<i;j++){
            if(a[i]==a[j]) z[j]--;
        }
    }
    sort(z,z+n+m);
    cout<<max(0,z[n+m-1])<<endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
        val s = readLine()!!.split(" ").map { it.toInt() }
        val sum = s.sum()
        val max = s.max()
        val m3 = max!!*3
     
        if(m3.mod(2) == 0 && sum.mod(2) == 0) {
            println((m3-sum)/2)
        } else if(m3.mod(2) == 1 && sum.mod(2) == 1) {
            println((m3-sum)/2)
        } else {
            println(((m3+3)-sum)/2)
        }
    }

Measured memory_bytes: 38036
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
vector<int> L;
vector<int> D;


int main(void){
    // Your code here!
    cin >> n >> m;
    L.resize(m);
    for(int i = 0; i < m ; i++){
        cin >> L[i];
    }
    
    sort(L.begin(), L.end(), greater<int>());
    D.resize(m-1);
    
    for(int i = 0; i < m-1; i++){
        D[i] = abs(L[i] - L[i+1]);
    }
    
    sort(D.begin(), D.end(), greater<int>());
    
    int cnt = 0;
    for(int i = 0; i < n-1; i++){
        if(i == m - 1) break;
        cnt += D[i];
    }
    
    cout << L[0] - L[m-1] - cnt << endl;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
template<typename ...Args> void read(Args&... args) { (cin >> ... >> args); }
template <typename...Args> void writeln(const Args &... args) { ((cout << args << " "), ...), cout << "\n"; }
template <typename...Args> void write(const Args &... args) { ((cout << args), ...), cout << "\n"; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> typename enable_if<is_same<decltype(declval<T>().size()), size_t>::value, int>::type operator~(const T& ct) { return (int)ct.size(); }
template <typename T, typename... Args> bool ckmax(T &a, const Args&... b) { return (a < max({b...})) ? (a = max({b...}), true) : false; }
template <typename T, typename... Args> bool ckmin(T &a, const Args&... b) { return (a > min({b...})) ? (a = min({b...}), true) : false; }
template <typename T> struct range {
    T u, v; bool inclusive;
    range(const T& _u, const T& _v, const bool& _inclusive = false) : u(_u), v(_v), inclusive(_inclusive) {}
    bool has(const T& w) { return (u <= w) and (inclusive ? (w <= v) : (w < v)); }
};
using vi = vector<int>;
using vb = vector<bool>;
using pii = pair<int, int>;
using vvi = vector<vector<int>>;
using vpii = vector<pii>;
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
template<typename T> using vv = vector<vector<T>>;
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T, vector<T>, less<T>>;
const int N = 200'0;
bitset<N* N> can;
auto soln() {
    can[0] = 1;
    int sum = 0;
    int n; read(n); vector<int> a(n); for(auto& i : a) { cin >> i; };
    for(auto i : a) {
        can |= (can << i);
        sum +=i;
    }
    for(int i = 1; i <= N * N; ++i){
        if(can[i] and (i >= sum - i)) {
            cout << i << "\n";
            return;
        }
    }
}
signed main() {
    int t = 1;
    { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); }
    while (t--)
        soln();
    return 0;
}


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

int main()
{
    long n, a;
    cin >> n;
    for (int i = 1; i <= n / i; i++)
        if (n % i == 0)
            a = i;
    cout << a + n / a - 2 << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
 
using namespace std;
 
int N,A,B,C,D;
int X_SET,Y_SET,X_SUM,Y_SUM;
int main(){
cin>>N>>A>>B>>C>>D;
X_SET = N/A;
if(N%A>0)X_SET=X_SET+1;
Y_SET=N/C;
if(N%C>0)Y_SET=Y_SET+1;
X_SUM=B*X_SET;
Y_SUM=D*Y_SET;
if(X_SUM<Y_SUM)cout<<X_SUM<<endl;
else
cout<<Y_SUM<<endl;
return 0;
}


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

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


int main(){
  int a,b=0,c;
  cin >> a;
  for(int i=1;i<=a;i++){
    for(int k=1;k<=a;k++){
      for(int j=1;j<=a;j++){
        c=gcd(i,j);
        if(c!=1){
          b=b+gcd(c,k);
        }
        if(c==1){
          b++;
        }
      }
    }
  }
  cout <<b;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
using namespace std;

int cnt[26];

signed main() {
	string s;
	cin >> s;
	
	int i;
	for (i = 0; i < 4; i++) cnt[s[i] - 'A']++;
	for (i = 0; i < 26; i++) {
		if (cnt[i] > 0 && cnt[i] != 2) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

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

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

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  ll n;cin>>n;
  cout<<n<<':';

  vector<ll> results;
  for(ll i=2; i*i<=n;i++){
    if(n%i==0)while(n%i==0){
      results.push_back(i);
      n /= i;
    }
  }
  if(n>1)results.push_back(n);

  for(auto p: results)cout<<' '<<p;

  cout<<endl;

  return 0;
}



Measured memory_bytes: 3172
#include <stdio.h>

int main(){
  int N,d[200002]={},A;
  scanf("%d",&N);
  for(int i=1;i<N;i++){
    scanf("%d",&A);
    d[A]++;
  }
  for(int i=1;i<=N;i++){
    printf("%d\n",d[i]);
  }
  return 0;
}

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

typedef long long ll;

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

    ll n;
    cin >> n;
    if(n%2==0) printf("%.10lf\n",1/2.0);
    else printf("%.10lf\n",((n/2+1)/(double)n));
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N, K, C; cin >> N >> K >> C;
    string s; cin >> s;
    
    int max_job = 0;
    vector<int> job_l(N+1);
    vector<int> job_r(N+1);
    for (int i = 0; i < N; i++) {
        if (s[i] == 'o') {
            job_l[i] = 1;
            i += C;
            max_job++;
        }
    }
    
    if (max_job > K) {
        return 0;
    }
    
    for (int i = N-1; i >= 0; i--) {
        if (s[i] == 'o') {
            job_r[i] = 1;
            i -= C;
        }
    } 
    
    for (int i = 0; i < N; i++) {
        if (job_r[i] && job_l[i]) {
            cout << i+1 << endl;
        }
    }
}


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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  LL n, l;
  deque<pair<LL, double>> cal;
  vector<LL> t, v;
  Solver(LL n) : n(n), t(n), v(n){};
  double temperature(int a, int b) {
    return (cal[b].second - cal[a].second) / (double)(cal[b].first - cal[a].first);
  }
  void solve() {
    cin >> l;
    for (int i = 0; i < n; ++i) {
      cin >> t[i] >> v[i];
    }
    cal.emplace_back(0, 0);
    for (int i = 0; i < n; ++i) {
      // increse
      cal.emplace_front(cal[0].first - v[i], cal[0].second - t[i] * v[i]);
      //answer
      DBG(cal)
      printf("%.9lf\n", temperature(0, cal.size() - 1));
      //mix
      while (cal.size() >= 3 && temperature(0, 1) < temperature(1, 2) - 1e-10) {
        cal.erase(cal.begin() + 1);
      }
      if (i == n - 1) break;
      //decrease
      LL upperBound = l - v[i + 1];
      while (1) {
        auto tmp = cal[cal.size() - 1];
        cal.pop_back();
        if (cal.back().first < cal[0].first + upperBound) {
          cal.emplace_back(cal[0].first + upperBound, cal.back().second + (tmp.second - cal.back().second) / (tmp.first - cal.back().first) * (cal[0].first + upperBound - cal.back().first));
          break;
        } else if (cal.back().first == cal[0].first + upperBound) {
          break;
        }
      }
      DBG(cal)
    }
  }
};

}  // namespace Problem

int main() {
  //std::cin.tie(0);
  //std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(9);
  long long n = 0;
  scanf("%lld", &n);

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


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

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
ll n,k;
cin>>n>>k;
vector<ll> a(n);
rep(i,n)cin>>a[i];
sort(a.begin(),a.end());
mint ans=0;
combination c(n+5);
rep(i,n){
	mint now=c(i,k-1);
//	cout<<now.x<<endl;
	ans+=now*a[i];
	ans-=now*a[n-i-1];
	//cout<<ans.x<<endl;
}
cout<<ans.x;

}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int h,w;
char S[25][25];
queue<Pi> q;
int dis[25][25];
int bfs(Pi s,Pi g){
	REP(i,25)REP(j,25)dis[i][j]=-1;
	dis[s.first][s.second]=0;
	q.push(s);
	while(q.size()){
		Pi t=q.front();q.pop();
		int x=t.first,y=t.second;
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(0<=nx&&nx<h&&0<=ny&&ny<w){
				if(S[nx][ny]=='.'){
					if(dis[nx][ny]==-1){
						dis[nx][ny]=dis[x][y]+1;
						q.push(Pi(nx,ny));
					}
				}
			}
		}
	}
	/*REP(i,h){
		REP(j,w){
			printf("%2d",dis[i][j]);
		}
		printf("\n");
	}
	printf("\n");*/
	return dis[g.first][g.second];

}

int main(){
	cin>>h>>w;
	REP(i,h){
		REP(j,w){
			cin>>S[i][j];
		}
	}
	int ret=0;
	REP(i,h){
		REP(j,w){
			REP(k,h){
				REP(l,w){
					if(S[i][j]=='.'&&S[k][l]=='.')
						ret=max(ret,bfs(Pi(i,j),Pi(k,l)));
				}
			}
		}
	}
	cout<<ret<<endl;
	return 0;
}

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

using namespace std;

typedef pair<int,int> P;
 
int main(){
    int n;
     
    while(cin >> n,n){
        vector<P> v;
        int sh,sm,ss,th,tm,ts,Max=0,Min = 99999,totals,totalt;
        for(int i = 0 ; i < n ; i++){
            scanf("%d:%d:%d" ,&sh , &sm , &ss);
            totals = sh*3600+sm*60+ss;
            v.push_back(P(totals,1));
            scanf("%d:%d:%d" ,&th , &tm , &ts);
            totalt = th*3600+tm*60+ts;
            v.push_back(P(totalt,-1));
        }
        sort(v.begin(),v.end());
     
        int ans = 0,tmp = 0;
        for(int i = 0 ; i < v.size() ; i++){
	    tmp += v[i].second;
	    ans = max(ans,tmp);
        }
        cout << ans << endl;
    }
    return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
ll LCM(int a, int b){
    return a*b/gcd(a,b);
}

int main(void){
    int n;
    ll r,g,b;
    string s;
    cin>>n>>s;
    r=g=b=0;
    rep(i,0,n){
        if(s[i]=='R')r++;
        else if(s[i]=='G')g++;
        else b++;
    }
    ll rgb=r*g*b;
    //cout<<rgb<<endl;
    rep(j,1,n){
        rep(i,0,j){
            int k=2*j-i;
            if(k<n){
                if(s[i]==s[j] || s[i]==s[k] || s[j]==s[k])continue;
                rgb--;
            }
        }
    }
    cout<<rgb<<endl;
    return 0;

}

Measured memory_bytes: 3624
import java.io.PrintWriter
import java.util.*
import java.math.*
import java.lang.*

val pw = PrintWriter(System.out)
val MOD: Long = (1e+9 + 7).toLong()

fun main(args: Array<String>) {
    val s = read() 
    val ans = "${s.first()}${s.length-2}${s.last()}"
    println(ans)
    pw.flush()
}

/****** Declared Functions and Data Structures ******/
// IO
fun read() = readLine()!!
fun readInt() = read().toInt()
fun readLong() = read().toLong()
fun readDouble() = read().toDouble()
fun readListOfString() = read().split(" ")
fun readListOfInt() = readListOfString().map { it.toInt() }
fun readListOfLong() = readListOfString().map { it.toLong() }
fun readListOfDouble() = readListOfString().map { it.toDouble() }

fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun Float.format(digits: Int) = String.format("%.${digits}f", this)

fun print(value: Any) { pw.print(value) }
fun println(value : Any) { pw.println(value) }

fun<T> permutations(src: List<T>): List<List<T>> {
    if(src.size == 1) return listOf(src)
    val perms = mutableListOf<List<T>>()
    val insertElement = src[0]
    permutations(src.drop(1)).forEach { perm ->
        for(i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, insertElement)
            perms.add(newPerm.toList())
        }
    }
    return perms
}

// return nCr, if you want nCr, please access v[n][r]
fun combinations(n: Long): List<List<Long>> {
    val v = (0..n).map { (0..n).map{0L}.toMutableList() }.toMutableList()
    for(i in 0 until v.size) {
        v[i][0] = 1L
        v[i][i] = 1L
    }
    for(i in 0 until v.size) {
        for(j in 1 until i) {
            v[i][j] = (v[i-1][j-1] + v[i-1][j] % MOD)
        }
    }
    return v.map { it.toList() }.toList()
}

// should be a >= b
fun gcd(a: Long, b: Long): Long = 
    if(b == 0L) a else gcd(b, a % b)

// shoud be a >= b
fun lcm(a: Long, b: Long): Long = 
    a / gcd(a, b) * b

fun sumDigits(num_: Long): Long {
    var num = num_
    var rtn: Long = 0
    while(num != 0.toLong()) {
        val tmp = num % 10
        rtn += tmp
        num /= 10
    }
    return rtn
}

fun isDecimal(v: Double): Boolean = ((v - Math.floor(v)) != 0.0)

// Data Structures
class Stack<T>(private var st: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = st.isEmpty()
    fun top(): T = st.last()
    fun push(e: T) { st.add(e) }
    fun pop() { st = st.dropLast(1).toMutableList() }
}

class Queue<T>(private var que: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = que.isEmpty()
    fun top(): T = que.first()
    fun push(e: T) { que.add(e) }
    fun pop() { que = que.drop(1).toMutableList() }
}


Measured memory_bytes: 33780
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int maxn=100100;
const int INF=0x3f3f3f3f;

int a[maxn],b[maxn],c[maxn],d[maxn];
int s[maxn],n;
int sa[maxn],h[maxn],rk[maxn];
int sum[maxn];
char str[maxn];
bool cmp(int r[],int a,int b,int k){
	return r[a]==r[b]&&r[a+k]==r[b+k];
}
void build_sa(int r[],int sa[],int n,int m){
	int i,j,p,*x=a,*y=b;
	for(i=0;i<m;c[i++]=0);
	for(i=0;i<n;c[x[i++]=r[i-1]]++);
	for(i=0;i<m;c[++i]+=c[i-1]);
	for(i=n-1;i>=0;sa[--c[x[i]]]=i--);
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;y[p++]=i++);
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<n;d[i++]=x[y[i-1]]);
		for(i=0;i<m;c[i++]=0);
		for(i=0;i<n;c[d[i++]]++);
		for(i=0;i<m;c[++i]+=c[i-1]);
		for(i=n-1;i>=0;sa[--c[d[i--]]]=y[i+1]);
		for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calh(int r[],int sa[],int n){
	int i,j,k=0;
	for(i=1;i<=n;rk[sa[i++]]=i-1);
	for(i=0;i<n;h[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);
}
int main(){
	int Q;
	scanf("%s",str);
	n=strlen(str);
	for(int i=0;i<n;i++)s[i]=(int)str[i];
	s[n]=0;
	build_sa(s,sa,n+1,256);
	calh(s,sa,n);
	
	int tot=0;
	for(int i=1;i<=n;i++){
		sum[i] = n-sa[i]-h[i];
		tot+=sum[i];
	}
	for(int i=2;i<=n;i++)
		sum[i]+=sum[i-1];
	int kth,ans;
		cin>>kth;
		if(kth>tot)kth%=tot;
		int L=0,R=n,mid;	
		while(L<=R){
			mid=(L+R)>>1;
			if(sum[mid]>=kth){
				ans=mid;R=mid-1;
			}else L=mid+1;
		}
		int s=sa[ans];
		int t=s+kth-sum[ans-1]+h[ans]-1;
		for(int i=s;i<=t;i++)cout<<str[i];
		cout<<endl;
}

Measured memory_bytes: 512
n,m=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(m)]

for i in range(10**n): #n桁の数字の全パターン
  number =str(i)
  if len(number)==n and all([number[s-1]==str(c) for s,c in sc]):
      print(number) #all すべての要素がTrueならTrue
      exit()
print(-1)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int, int>;

int main() {
  int N, S=0;
  cin >> N;
  vector<int> T(N);
  for (int i=0; i<N; i++) {
    cin >> T[i];
    S+=T[i];
  }
  int M;
  cin >> M;
  int p, x, m=0;
  for (int i=0; i<M; i++) {
    cin >> p >> x;
    cout << S-T[p-1]+x << endl;
  }
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

ll n;
vector<vector<ll>> g(300);
ll color[300] = {};
bool dfs(ll v, ll c){
    color[v] = c;
    rep(i, g[v].size()){
        if(color[g[v][i]]==c)return false;
        if(color[g[v][i]]==0 && !dfs(g[v][i], -c))return false;
    }
    return true;
}
int main(){
    cin >> n;
    vector<string> s(n);
    rep(i, n)cin >> s[i];
    rep(i, n)rep(j, n)if(s[i][j]=='1')g[i].push_back(j);

    rep(i, n){
        if(color[i]==0 && !dfs(i, 1)){
            cout << -1;
            return 0;
        }
    }

    queue<ll> que;
    vector<ll> ans;
    rep(i, n){
        vector<ll> dist(n, -1);
        dist[i]=0;
        que.push(i);
        while(!que.empty()){
            ll v = que.front();
            que.pop();
            rep(j, g[v].size()){
                ll nv = g[v][j];
                if(dist[nv]!=-1)continue;
                dist[nv]=dist[v]+1;
                que.push(nv);
            }
        }
        sort(ALL(dist), greater<ll>());
        ans.push_back(dist.front());
    }
    sort(ALL(ans), greater<ll>());
    cout << ans.front()+1 << endl;
}

Measured memory_bytes: 768
// D - Decayed Bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

class DisjointSet {
public:
	vector<int> rank;
	vector<int> parent;

	DisjointSet() {}

	// 0, 1, ... size-1 をそれぞれ唯一の要素とする
	// size個の互いに素な集合を作成
	DisjointSet(int size) {
		rank.resize(size, 0);
		parent.resize(size, 0);
		for (int i=0; i<size; i++) {
			makeSet(i);
		}
	}

	// 要素がXただ一つである新しい集合を作る
	void makeSet(int x) {
		parent[x] = x;
		rank[x] = 0;
	}

	// xとyが同じ集合に属しているかを判定する
	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	// 指定された2つの要素x, yを合併する
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	// 低い方の木を高い方の木に合併
	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			parent[y] = x;
		} else {
			parent[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	// 要素xが属する集合の代表の要素を求める
	int findSet(int x) {
		if (x != parent[x]) {
			parent[x] = findSet(parent[x]);
		}
		return parent[x];
	}
};

int A[500000];
int B[500000];
int n_connected[500000];
ll inconvinience[500000];

ll convinience(ll n) {
	return n * (n-1) / 2;
}

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

	for (int i=0; i<M; i++) {
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}

	reverse(A, A+M);
	reverse(B, B+M);

	for (int i=0; i<N; i++) {
		n_connected[i] = 1;
	}

	DisjointSet ds = DisjointSet(N);
	inconvinience[0] = convinience(N);
	for (int i=0; i<M-1; i++) {
		if (ds.same(A[i], B[i])) {
			inconvinience[i+1] = inconvinience[i];
		} else {
			int n_A = n_connected[ds.findSet(A[i])];
			int n_B = n_connected[ds.findSet(B[i])];
			int n_C = n_A + n_B;
			ds.unite(A[i], B[i]);
			int C = ds.findSet(A[i]);
			n_connected[C] = n_C;
			inconvinience[i+1] = inconvinience[i] + convinience(n_A) + convinience(n_B) - convinience(n_C);
		}

	}

	reverse(inconvinience, inconvinience+M);

	for (int i=0; i<M; i++) {
		cout << inconvinience[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  if(s=="RRR")
    cout<<3;
  else if(s=="RRS" || s=="SRR")
    cout<<2;
  else if(s=="RSS" || s=="SRS" || s=="SSR" || s=="RSR")
    cout<<1;
  else
    cout<<0;
}

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

int main(){
  int n;
  int x;
  int y;

  scanf("%d", &n);

  x = 800*n;
  y = n/15*200;

  printf("%d\n", x - y);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mod 1000000007
#define mx 1000002
mt19937 myrand(time(0));

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    string s,t;
    cin>>s;
    cin>>t;
    ll ans=1e18;
    for(int i=0;i<(int)s.size();i++){
        if((i+(int)t.size())>(int)s.size()) break;
        ll tmp=0;
        for(int j=0;j<(int)t.size();j++){
            if(s[i+j]!=t[j]) tmp++;
        }
        ans=min(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int N,H;
	cin >> N>>H;
	
	cout << (N + H) % 24 << endl;
	return 0;
}



Measured memory_bytes: 256
#!/usr/bin/ruby
def Z(a,i)b=[];1.step(i){b<<$x;$x+=1}
b.reverse!if$c>0
$c^=1;a<<b
end
t=0
while(n=gets.to_i)>0
puts"Case #{t+=1}:"
a=[];$x=$c=1
1.step(n){|i|Z(a,i)}
(n-1).step(1,-1){|i|Z(a,i)}
n.times{|i|n.times{|j|printf("%3d",a[i+j].shift)};puts}
end

Measured memory_bytes: 5336
#include<iostream>
#include<algorithm>

using namespace std;

int main() {
  int N;
  int K;
  cin >> N >> K;
  K--;
  int h[N];
  for(int i = 0; i < N; i++){
    cin >> h[i];
  }
  sort(h, h + N);
  int min = h[K]-h[0];
  for(int i = 0 ; i < N - K; i++){
    int sub = h[i+K] - h[i];
    if(sub < min) min = sub;
  }
  cout << min << endl;
  return 0;
}


Measured memory_bytes: 640
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve
int a[3][100001];
ll dp[100001][3];

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  rep(i, n){
    rep(j, 3)cin >> a[j][i];
  }
  rep(i, n){
    rep(j, 3){
      rep(k, 3){
        if(j == k)continue;
        dp[i+1][j] = max(dp[i+1][j], dp[i][k] + a[j][i]);
      }
    }
  }
  cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
	return 0;
}


Measured memory_bytes: 3712