akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MAX_V 200
#define INF LONG_LONG_MAX

// 行き先、容量、逆辺(反対側の辺)
struct edge{int to, rev; ll cap;};

vector<edge> G[MAX_V];  //グラフ
ll level[MAX_V];   //sからの距離
int iter[MAX_V];   //どこまで調べ終わったか

// fromからtoへ向かう容量capの変をグラフに追加する
void add_edge(int from, int to, ll cap){
    G[from].push_back((edge){to, G[to].size(), cap});
    G[to].push_back((edge){from, G[from].size()-1, 0});
}

// sからの最短距離をBFSで計算する
void bfs(int s){
    fill(level, level+MAX_V, -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[e.to] < 0){
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

// 増加パスをDFSで探す
ll dfs(int v, int t, ll f){
    if(v == t)  return f;
    for(int &i = iter[v]; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            ll d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}


ll max_flow(int s, int t){
    ll flow = 0;
    for(;;){
        bfs(s);
        if(level[t] < 0){
            return flow;
        }
        fill(iter, iter+MAX_V, 0);
        ll f;
        while((f = dfs(s, t, INF)) > 0){
            flow += f;
        }
    }
}



int main(){
    int N;
    cin >> N;
    ll a_sum = 0;
    for(int i = 1; i <= N; i++){
        ll a; cin >> a;
        if(a > 0){
            add_edge(0, i, 0);
            add_edge(i, N+1, a);
            a_sum += a;
        }
        else{
            add_edge(0, i, -a);
            add_edge(i, N+1, 0);
        }
        int j = 2;
        while(i*j <= N){
            add_edge(i, i*j, (ll)1e12 + 10);
            j++;
        }
    }

    ll f = max_flow(0, N+1);
    cout << a_sum - f << endl;


    return 0;

}


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

int main() {
  ll N;
  cin >> N;
  ll L = 0; //全長
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    ll a;
    cin >> a;
    L += a;
    A[i] = a;
  }
  vector<vector<ll>> B(2, vector<ll>(N-1));
  priority_queue<ll, vector<ll>, greater<ll>> ans;
  B[0][0] = A[0];
  B[1][0] = L - A[0];
  ans.push(abs(B[1][0] - B[0][0]));
  for (int i = 1; i <= N-2; i++) {
    B[0][i] = B[0][i-1] + A[i];
    B[1][i] = L - B[0][i];
    ans.push(abs(B[1][i] - B[0][i]));
  }
  cout << ans.top() << endl;
}

  

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

const int N=1e5+10;
int n;
struct Node{
    int ind,w;
    bool operator < (const Node &t) const{
        return w < t.w;
    }
}a[N];

int main(){
    int res;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].w);
        a[i].ind = i;
    }
    sort(a+1,a+n+1);
    res=0;
    for(int i=1;i<=n;i++)
        if( !(i&1) && a[i].ind&1) res++;
    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
    while(1){
        int N;
        cin >> N;
        if(N==0) break;
        vector<int> A(N,0);
        for(int i=0;i<N;i++){
            cin >> A[i];
        }
        int M=0;
        int m=1000;
        int sum=0;
        for(int i=0;i<N;i++){
            sum+=A[i];
            if(M<A[i]){M=A[i];}
            if(m>A[i]){m=A[i];}
        }
        cout << (sum-M-m)/(N-2) << endl;
    }
}



Measured memory_bytes: 3100
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
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;}

int main(){
	string s;
	cin >> s;
	
	if(s[0]==s[1] && s[1]==s[2] && s[2]=='R'){
		cout << 3 << endl;
	}else if(s[0]==s[1] && s[1]=='R' || s[1]==s[2] && s[2]=='R'){
		cout << 2 << endl;
	}else if(s[0]==s[1] && s[1]==s[2] && s[2]=='S'){
		cout << 0 << endl;
	}else{
		cout << 1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3624
// ABC083A
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        String ans = "Left";
        if (n + b < c + d) {
            ans = "Right";
        } else if (n + b == c + d) {
            ans = "Balanced";
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define maxn 100
#define maxk 100001
#define mod 1000000007
using namespace std;

int n,k;
int ar[maxn];
int dp[maxk];
int add[maxk];

int main() {
	cin >> n >> k;
	for( int i = 0 ; i < n ; i++ )
		cin >> ar[i];
	dp[0] = 1;
	for( int i = 0 ; i < n ; i++ ) {
		memset( add , 0 , sizeof(add) );
		for( int j = k ; j >= 0 ; j-- ) {
			add[j] = ( add[j] + dp[j] ) % mod;
			if( j+ar[i]+1 <= k )
				add[j+ar[i]+1] = ( add[j+ar[i]+1] - dp[j] + mod ) % mod;
		}
		int sum = 0;
		for( int j = 0 ; j <= k ; j++ ) {
			sum = ( sum + add[j] ) % mod;
			dp[j] = sum;
		}
	}
	cout << dp[k] << endl;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;
const double PI = acos(-1);

struct UnionFind {
	//親の番号
	//ex) par[3]=2 //3の親が2
	std::vector<int> par;

	//要素数Nで初期化
	UnionFind(int N)
		: par(N)
	{
		for (int i = 0; i < N; i++) {
			par[i] = i;
		}
	}

	//xの木の根を求める
	int root(int x) {
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	//xとyの木を併合
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		//根が異なるとき、rxをryの根に付ける
		if (rx != ry) {
			par[rx] = ry;
		}
	}

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/
	
	int n, m;
	cin >> n >> m;
	vector<int> p(n);
	rep(i, n) cin >> p[i];
	
	UnionFind uf(n + 1);

	rep(i, m) {
		int x, y;
		cin >> x >> y;
		uf.unite(x, y);
	}

	int ans = 0;
	rep(i, n) {
		if (uf.same(i + 1, p[i])) {
			ans++;
		}
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 1152
from collections import Counter
n, cnt, mx, arr = int(input()), Counter(), -1, []
for i in range(n):
    s = input()
    arr.append(s)
    cnt[s] += 1
    mx = max(mx,cnt[s])
res = []
for i in arr:
    if cnt[i] == mx:
        res.append(i)
        cnt[i] = 0
res.sort()
for i in res:
    print(i)

Measured memory_bytes: 33740
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int main(int argc, char* argv[]) {
  int N, A, B, C;
  std::cin >> N >> A >> B >> C;
  std::vector<int> ls(N);
  for (auto&& l : ls) {
    std::cin >> l;
  }
  // NOTE: return cost(MP)
  std::function<int(int cur, int a, int b, int c)> dfs;
  dfs = [&](int cur, int a, int b, int c) {
    if (cur == N) {
      if (a > 0 && b > 0 && c > 0) {
        // NOTE: 対象となる竹のベースが存在し，0ベースとの合成(10MPx3)分のコストを差し引く
        // NOTE: 竹を使用することを0lengthとの合成として考えていたため
        return std::abs(a - A) + std::abs(b - B) + std::abs(c - C) - 30;
      } else {
        return static_cast<int>(1e8);
      }
    }
    // NOTE: not use ls[cur]
    int ret0 = dfs(cur + 1, a, b, c);
    // NOTE: use ls[cur] (concat)
    int ret1 = dfs(cur + 1, a + ls[cur], b, c) + 10;
    int ret2 = dfs(cur + 1, a, b + ls[cur], c) + 10;
    int ret3 = dfs(cur + 1, a, b, c + ls[cur]) + 10;
    return std::min(ret0, std::min(ret1, std::min(ret2, ret3)));
  };
  std::cout << dfs(0, 0, 0, 0) << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define mp            make_pair
#define PI            3.14159265
#define M             1000000007
#define MM            998244353
#define fr            first
#define sc            second
#define all(v)        (v).begin(),(v).end()
#define rall(v)       (v).rbegin(),v.rend()
#define vc            vector
#define vi            vector<int>
#define pii           pair<int,int>
#define psi           pair<string,int>
#define pis           pair<int,string>
#define mii           map<int,int>
#define msi           map<string,int>

int solve(){
    int n,ans=0; cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    for (int i = 1; i < n-1; ++i)
    {
        if((a[i]<a[i-1]&&a[i]>a[i+1])||(a[i]>a[i-1]&&a[i]<a[i+1])) ans++;
    }
    cout<<ans;
}

signed main() {
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 256
k = int(input())
s = str(input())

mod = 1000000007
decided_keta = len(s)
all_keta = len(s) + k

kai_list = [1 for i in range(2000010)]
for i in range(2,len(kai_list)):
    kai_list[i] = (kai_list[i-1]*i)%mod

answer = 0
for last_given_character_posi in range(decided_keta-1,all_keta):
    given_posi_pattern = kai_list[last_given_character_posi]*pow(kai_list[decided_keta-1],mod-2,mod)%mod*pow(kai_list[last_given_character_posi-decided_keta+1],mod-2,mod)%mod
    char_pattern = pow(25,last_given_character_posi-(decided_keta-1),mod)
    rest_char_pattern = pow(26,all_keta-(last_given_character_posi+1),mod)
    answer = (answer + given_posi_pattern*char_pattern%mod*rest_char_pattern%mod)%mod
print(answer)

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

int N;

int main()
{
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    vector<int> s = a;

    sort(s.rbegin(), s.rend());
    for (int i = 0; i < N; i++) 
    {
        int ans = s[0];
        if (s[0] == a[i]) ans = s[1];
        cout << ans << endl;
    }
}

Measured memory_bytes: 3200
n_squares = int(input().strip())

list_squares = [int(x) for x in input().strip().split()]

new_list = [0 for x in range(n_squares)]

for i in range(1, n_squares):
    if list_squares[i] <= list_squares[i - 1]:
        new_list[i] = new_list[i - 1] + 1

print(max(new_list))


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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

struct sta {
	LL d;
	int x;
	int y;
	bool operator<(const sta &a)const {
		return d>a.d;
	}
};

int main() {
	int h, w;
	LL a, b;
	cin >> h >> w >> a >> b;
	vector<string> f(h);
	int sx, sy, gx, gy;
	for (int i = 0; i<h; i++) {
		cin >> f[i];
		for (int j = 0; j<w; j++) {
			if (f[i][j] == 's') {
				sx = j, sy = i;
			}
			else if (f[i][j] == 'g') {
				gx = j, gy = i;
			}
		}
	}
	priority_queue<sta> dijk;
	vector<vector<LL>> dist(h, vector<LL>(w, LINF));
	dijk.push({ 0,sx,sy });
	sta now;
	vector<int> vx1 = { 0,0,1,-1 }, vy1 = { 1,-1,0,0 };
	vector<int> vx2 = { 1,-1,1,-1 }, vy2 = { 1,-1,-1,1 };
	bool ok;
	int nx, ny;
	while (!dijk.empty()) {
		now = dijk.top();
		dijk.pop();
		if (now.x == gx && now.y == gy) {
			cout << now.d << endl;
			return 0;
			// break;
		}
		if (dist[now.y][now.x] != LINF) continue;
		dist[now.y][now.x] = now.d;
		ok = true;
		if (f[now.y][now.x] == '*') ok = false;
		for (int i = 0; i<4; i++) {
			nx = now.x + vx1[i];
			ny = now.y + vy1[i];
			if (0 <= nx && nx<w && 0 <= ny && ny<h) {
				if (dist[ny][nx] == LINF && f[ny][nx] != '#') {
					dijk.push({ now.d + a,nx,ny });
					// cout << nx SP ny << endl;
				}
				if (f[ny][nx] == '*') {
					ok = false;
				}
			}
		}
		for (int i = 0; i<4; i++) {
			nx = now.x + vx2[i];
			ny = now.y + vy2[i];
			if (0 <= nx && nx<w && 0 <= ny && ny<h) {
				if (f[ny][nx] == '*') {
					ok = false;
				}
			}
		}
		if (ok) {
			for (int i = 0; i<4; i++) {
				nx = now.x + vx1[i];
				ny = now.y + vy1[i];
				if (0 <= nx && nx<w && 0 <= ny && ny<h) {
					if (dist[ny][nx] == LINF) {
						dijk.push({ now.d + a + b,nx,ny });
					}
				}
			}
			for (int i = 0; i<4; i++) {
				nx = now.x + vx2[i];
				ny = now.y + vy2[i];
				if (0 <= nx && nx<w && 0 <= ny && ny<h) {
					if (dist[ny][nx] == LINF) {
						dijk.push({ now.d + 2 * a + b,nx,ny });
					}
				}
			}
		}
	}
	// for(int i=0;i<h;i++){
	//   for(int j=0;j<w;j++){
	//     cout << dist[i][j] << " ";
	//   }
	//   cout << endl;
	// }
	cout << "INF" << endl;
	return 0;
}




Measured memory_bytes: 11936
H,W,K = map(int,input().split())

S = [0] * H
data = [[0]*W for i in range(H)]

for i in range(H):
    S[i] = list(map(int,list(str(input()))))

data[0][0] = S[0][0]

for i in range(1,W):
    data[0][i] = data[0][i-1] + S[0][i]

for i in range(1,H):
    data[i][0] = data[i-1][0] + S[i][0]

for i in range(1,H):
    for j in range(1,W):
        data[i][j] = data[i-1][j] + data[i][j-1] - data[i-1][j-1] + S[i][j]

#print(S)
#print(data)

m = 10**4
for i in range(2**(H-1)):
    cross = []
    tate = []
    for j in range(H-1):
        if i&(2**j) == 2**j:
            cross.append(j)
    #print(cross)
    
    det2 = 0
    start = 0
    for j in range(W):
        det = 0
        if len(cross) > 0:
            for k in range(len(cross)):
                if (k == 0 and start == 0 and data[cross[k]][j] > K):
                    det = -1
                    break
                elif (k == 0 and start != 0 and data[cross[k]][j] - data[cross[k]][start-1] > K):
                    det = -1
                    break
                elif (start == 0 and k != 0 and data[cross[k]][j]-data[cross[k-1]][j] > K):
                    det = -1
                    break
                elif (start != 0 and k != 0 and data[cross[k]][j]-data[cross[k]][start-1]-data[cross[k-1]][j]+data[cross[k-1]][start-1] > K):
                    det = -1
                    break
            if (start == 0 and data[H-1][j] - data[cross[-1]][j]> K):
                det = -1
            elif (start != 0 and data[H-1][j]-data[cross[-1]][j]-data[H-1][start-1]+data[cross[-1]][start-1] > K):
                det = -1
        #if i == 2**(H-1)-1:
        #    print("k",k,start,det)
        else:
            if (start == 0 and data[H-1][j] > K):
                det = -1
            elif (start != 0 and data[H-1][j] - data[H-1][start-1] > K):
                det = -1
        if det == -1:
            if j == start:
                det2 = -1
                break
            else:
                tate.append(j-1)
                start = j
        #if i == 2**(H-1)-1:
        #    print("tate",tate)
    
    if det2 == 0:
        #print(start,len(cross)+len(tate))
        m = min(m,len(cross)+len(tate))

print(m)

Measured memory_bytes: 46940
fn main() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let mut v: Vec<u32> = input.trim().split_whitespace()
        .map(|x| x.parse().unwrap()).collect();
    let mut ans = 0;
    let mut i = 2;
    loop {
        if ( i == 0 ) {
            break;
        }
        if ( v[0] >= v[1]) {
            ans += v[0];
            v[0] -= 1;
        } else {
            ans += v[1];
            v[1] -= 1;
        }
        i -= 1;
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int clz(int x) { return 31 - __builtin_clz(x); }
int clz(ll x) { return 63 - __builtin_clzll(x); }
int ctz(int x) { return __builtin_ctz(x); }
int ctz(ll x) { return __builtin_ctzll(x); }

class compare {
public:
	bool operator()(tuple<ll, ll> a, tuple<ll, ll> b) {
		return (get<1>(a) > get<1>(b));
	}
};

ll dp[401][401];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,sum=0;
	cin>>n;
	rep(i,400)	rep(j,400) dp[i][j]=LINF;
	vl v(n),r(n+1);
	rep(i,n)cin>>v[i],sum+=v[i],r[i+1]=sum,dp[i][i]=0;
	range(j,1,n+1){
		for(int i=0;i+j<n;i++){
			rep(k,j){
				dp[i][i+j]=min(dp[i][i+j],(r[i+j+1]-r[i])+dp[i][i+k]+dp[i+k+1][i+j]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
}

Measured memory_bytes: 1536
#include<cstdio>

int a[10];

bool dfs(int ite,int l,int r){
    if(ite==10){
        return true;
    }else if(a[ite]>l&&dfs(ite+1,a[ite],r)){
        return true;
    }else if(a[ite]>r&&dfs(ite+1,l,a[ite])){
        return true;
    }else{
        return false;
    }
}

bool solve(){
    for(int i=0;i<10;i++){
        scanf("%d",a+i);
    }
    return dfs(0,0,0);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        if(solve()) printf("YES\n");
        else printf("NO\n");
    }
}

Measured memory_bytes: 1008
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1000000007;
int main() {
	ll i,j,k,l,m,n,t,w;
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> w;

  vector<pair<ll, ll> > weights(n);
  for (i = 0; i < n; i++){
    cin >> j >> k;
    weights[i] = make_pair(j, k);
  }

  vector<ll > dp(w+1, -1);

  ll ans = 0;
  dp[0] = 0;
  for (i = 0; i < n; i++)
  {
    vector<ll > newDP(w+1, -1);
    for (j = 0; j <= w; j++){
      ll weight = weights[i].first, value = weights[i].second;
      newDP[j] = max(newDP[j], dp[j]);
      if (dp[j]==-1 || j > w - weight)
      {
        continue;
      }
      newDP[j + weight] = max(newDP[j + weight], dp[j] + value);
      // cout << i << ' ' << j << ' ' << dp[j] << ' ' << weight << ' ' << newDP[j + weight] << endl;
    }
    dp = newDP;
  }
  for (i = 0; i <= w; i++){
    ans = max(ans, dp[i]);
  }
    cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1804
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using bint = boost::multiprecision::cpp_int;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
#define rrepSE(i,s,e) for (int i = (s); i > (e); i--)
#define ssort(v) sort(v.begin(), v.end())
#define gsort(v) sort(v.rbegin(), v.rend())
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
#define DEBUG_PRINT(var) std::cout << #var << " = " << var << "\n";

int main()
{
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    ssort(l);
    int ans = 0;
    rep(i,n-1) repSE(j,i+1,n-1) {
        int idx = lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin();
        ans += idx - j - 1;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3556
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory>
#include <cstring>
#include <cassert>
#include <numeric>
#include <sstream>
#include <complex>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define REP2(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(S) (S).begin(), (S).end()

template <typename T, typename E>
ostream &operator<<(std::ostream &os, const std::pair<T, E> &p){
  return os << "(" << p.first << ", " << p.second << ")";
}

typedef long long ll;

const ll  mod = 1000 * 1000 * 1000 + 7;
const int MAX = 51;
int na, nt, ng, nc;
int m;
map<string, vector<string> > rules;
vector<int> cands;
ll memo[MAX][MAX][MAX][MAX];

void dfs(string symbol){
  if ((int)cands.size() > na + nt + ng + nc) return;

  for (auto str : rules[symbol]){
    if (str[0] == '['){
      int cand = 0;
      for (auto c : str){
        switch (c){
        case 'A': cand |= 1; break;
        case 'T': cand |= 2; break;
        case 'G': cand |= 4; break;
        case 'C': cand |= 8; break;
        }
      }
      cands.push_back(cand);
    } else {
      dfs(str);
    }
  }
}

ll rec(int a, int t, int g, int c){
  int pos = a + t + g + c;
  if (pos == na + nt + ng + nc) return 1;
  if (memo[a][t][g][c] != -1) return memo[a][t][g][c];
  
  ll &res = memo[a][t][g][c] = 0;
  if (a < na && (cands[pos] & 1)) res += rec(a + 1, t, g, c);
  if (t < nt && (cands[pos] & 2)) res += rec(a, t + 1, g, c);
  if (g < ng && (cands[pos] & 4)) res += rec(a, t, g + 1, c);
  if (c < nc && (cands[pos] & 8)) res += rec(a, t, g, c + 1);
  res %= mod;
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  while (cin >> na >> nt >> ng >> nc && na + nt + ng + nc){
    cands.clear();
    rules.clear();
    memset(memo, -1, sizeof(memo));
    string start_symbol = "";

    
    cin >> m;
    REP(i, m){
      string str;
      cin >> str;
      string symbol(str.begin(), str.end() - 1);

      if (start_symbol == ""){
        start_symbol = symbol;
      }
      
      getline(cin, str);
      istringstream iss(str);
      while (iss >> str) rules[symbol].push_back(str);
    }

    dfs(start_symbol);
    cout << ((int)cands.size() == na + nt + ng + nc ? rec(0, 0, 0, 0) : 0) << endl;
  }
  return 0;
}

Measured memory_bytes: 54148
#include <bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define sz size()
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)

#define ll long long

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.in","r",stdin);

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

    int x = v[0];
    ll br = 0ll;
    for (i=1;i<n;i++) {
        if (v[i]<x) {
            br+=x-v[i];
            v[i] = x;
        }

        if (v[i]>x)
            x = v[i];
    }

    cout<<br<<"\n";

    return 0;
}

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

typedef long long ll;

ll i,j,k,m,n,ans,num;

bool solve(){
	cin >> n;
	string s[55];
	if(n == 0)return false;
	ll c = 0;
	ll d = 0;
	for(i=0;i<n;i++){
		cin >> s[i];
		c = s[i].size();
		d = max(c,d);
	}
	ans = -1;
	for(j=1;j<=d;j++){
		string t[55];
		for(i=0;i<n;i++){
				
				m = s[i].size();
				bool flag = false;
				num = 0;
				for(k=0;k<m;k++){
					if(k == 0 || flag){
						t[i] = t[i] + s[i][k];
						num++;
						//cout << "!" << endl;
						if(num == j)break;
					}
					if(s[i][k] == 'a' || 
						s[i][k] =='i'|| 
						s[i][k] == 'u' || 
						s[i][k] == 'e' || 
						s[i][k] == 'o'){
						flag = true;
					}else{
						flag = false;
					}
				}
		}
		sort(t,t+n);
		bool dame = false;
		//cout << j << " " << t[0] << " " << t[1] << " " << endl;
		for(i=0;i<n-1;i++){
			if(t[i] == t[i+1]){
				dame = true;
			}
		}
		if(!dame){
			ans = j;
			break;
		}

	}

	cout << ans << endl;
		}



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

}


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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
n, m = map(int, input().split())
x=list(map(int, input().split()))
x.sort()
#print(x)
sa=[]
for i in range(m-1):
    sa.append(x[i+1]-x[i])
sa.sort()
if n<m:
    print(sum(sa[:m-n]))
else:
    print(0)

Measured memory_bytes: 13188
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>

#define rep(i,j,k) for(int i=j;i<k;i++)
#define drep(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
#define Sort(x) sort((x).begin(),(x).end())
#define fi first
#define se second
#define vi vector<int>
#define INF 1000000000
#define MOD 1000000009
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

ll gcd(ll a,ll b){
    if(a<b){
        int t=a;a=b;b=t;
    }
    int c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}

ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}

bool isPrime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    for(int i=3;i<=sqrt(x);i+=2){
        if(x%i==0)return false;
    }
    return true;
}

int kaizyo(int x){
    if(x==1)return x;
    else return x*kaizyo(x-1);
}

typedef struct Point{
    int x;
    int y;
} P;

int main() {
    double a,b;
    cin>>a>>b;
    cout<<ceil((a+b)/2)<<endl;
    
    


    return 0;
}


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

const int N = 110;
const long double INF = 1e12;
const long double PI = acos(-1.0);
inline long double sqr(long double x){return x * x;}

int x[N], y[N];
long double ans[N];

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i){
		scanf("%d%d", &x[i], &y[i]);
	}
	std::vector <long double> vec = {0, 2 * PI};
	for (int i = 0; i < n; ++ i){
		for (int j = i + 1; j < n; ++ j){
			long double angle = std::atan2(y[j] - y[i], x[j] - x[i]) + PI / 2;
			while (angle < 0) angle += PI;
			while (angle >= PI) angle -= PI;
			vec.push_back(angle);
			vec.push_back(angle + PI);
		}
	}
	std::sort(vec.begin(), vec.end());
	for (int i = 0, sz = vec.size(); i < sz - 1; ++ i){
		long double min = 1e200, angle = (vec[i] + vec[i + 1]) / 2;
		long double xx = INF * std::cos(angle), yy = INF * std::sin(angle);
		int sit;
		for (int j = 0; j < n; ++ j){
			long double dis = sqr(xx - x[j]) + sqr(yy - y[j]);
			if (dis < min){
				min = dis;
				sit = j;
			}
		}
		ans[sit] += vec[i + 1] - vec[i];
	}
	for (int i = 0; i < n; ++ i){
		printf("%.10lf\n", (double) ans[i] / (2 * (double) PI));
	}
	return 0;
}

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

using namespace std;

int main() {
  int n; cin>>n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }

  int cnt = 0;
  for (int i = 1; i < n-1; i++) {
    if ((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i-1] > p[i] && p[i] > p[i+1])) cnt++;
  }

  cout << cnt << endl;

  return 0;
}


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

#include <fstream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  /*
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
  //*/
  int N;
  cin >> N;
  int ans = 0;
  for(int i = 1; i <= N; i+=2){
    int cnt = 0;
    for(int j = 1; j <= i; j++){
      if(i % j == 0){
        cnt++;
      }
    }
    if(cnt == 8){
      ans++;
    }
  }
  cout << ans <<endl;
}

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

#define int long long
#define pb push_back
#define in insert
#define F first
#define S second
#define mod 1000000007
#define endl '\n'
#define all(x)  x.begin(),x.end()
#define w(x) int x;cin>>x; while(x-->0)
#define memset(a,b) memset(a,b,sizeof(a))
#define debug(x) cout << "[ " << #x  << " : " << x << " ]" << endl;

void fast()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
/*
think fast
think simple
*/
string arr[] = {"AC", "WA", "TLE",  "RE"};
void mysol()
{
	map<string, int>m;
	w(q)
	{
		string a; cin >> a;
		m[a]++;
	}
	for (auto a : arr)
	{
		cout << a << " x " << m[a] << endl;
	}
}

int32_t main()
{
	fast();
	// w(t)
	{
		mysol();
	}
	//cerr << sizeof(dp)*(1e-6) << " megabytes\n";
	return 0;
}


Measured memory_bytes: 3688
n = int(input())
s = list(map(int, input()))

rr = {}
r = set()
for i in range(len(s) - 1, 0, -1):
    t = s[i]
    r.add(t)
    rr[i] = r.copy()

a = [[set() for j in range(10)] for i in range(10)]
l = set()
for i in range(1, len(s) - 1):
    t = s[i]
    l.add(s[i-1])
    r = rr[i+1]
    for j in l:
        a[t][j] |= r

ans = 0
for b in a:
    for c in b:
        ans += len(c)
print(ans)

Measured memory_bytes: 27856
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll pw(ll a, ll b) {
    if (b == 0) return 1;
    ll t = pw(a, b / 2);
    if (b % 2 == 0) return (t * t)%mod;
    else return ((t * t)%mod * a)%mod;
}
int main()
{
	int n,k;cin>>n>>k;
	int a[n+1];for(int i=0;i<n;i++)cin>>a[i];
	int dp[n];for(int i=0;i<n;i++)dp[i]=1e9+7;
	dp[0]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;i-j>=0&&j<=k;j++)
		{
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
		}
	}
	cout<<dp[n-1]<<endl;
}


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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    for(int i=0;i<N;i++){
        if(A[i]%2 == 1){
            cout <<"first" << endl;
            return 0;
        }
    }
    cout <<"second"<<endl;
        

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <queue>

int N;
std::string S;

int main() {
  std::cin >> N;
  std::string S;  std::cin >> S;
  std::priority_queue<int, std::vector<int>, std::greater<int> > pqw;
  std::priority_queue<int> pqr;
  for (int i = 0; i < N; ++i) {
    if (S[i] == 'W')
      pqw.push(i);
    else
      pqr.push(i);
  }

  if (pqw.size() == 0 or pqr.size() == 0) {
    std::cout << "0\n";
    return 0;
  }

  int ans = 0;
  while (pqw.top() < pqr.top()) {
    int w = pqw.top();  pqw.pop();
    int r = pqr.top();  pqr.pop();
    pqw.push(r);
    pqr.push(w);
    ans++;
  }

  std::cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 4688
import sys
input=sys.stdin.readline
H, W = [int(x) for x in input().split()]
board = []
for _ in range(H):
    board.append(input())

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if board[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

for i in range(H):
    for j in reversed(range(W)):
        if board[i][j] == '.':
            if j == W - 1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

for j in range(W):
    for i in range(H):
        if board[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1

for j in range(W):
    for i in reversed(range(H)):
        if board[i][j] == '.':
            if i == H - 1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1

ans = 0
for i in range(H):
    for j in range(W):
        cand = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, cand)
        
print(ans)

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

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

    long long n, m;
    long long k;
    cin >> n >> m >> k;
    vector<long long> A(n + 1), B(m);
    for(long long i = 0; i < n; i++){
        cin >> A[i + 1];
    }
    for(long long i = 0; i < m; i++){
        cin >> B[i];
    }

    for(long long i = 1; i <= n; i++){
        A[i] += A[i - 1];
    }
    for(long long i = 1; i < m; i++){
        B[i] += B[i - 1];
    }

    long long ans = 0;
    for(long long i = 0; i <= n; i++){
        long long now = k - A[i];
        if(now < 0) continue;
        long long idx = upper_bound(B.begin(), B.end(), now) - B.begin();
        ans = max(ans, i + idx);
    }

    cout << ans << endl;

    return 0;
}

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

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int main(){
    int n;
    scanf("%d", &n);
    lint L[n], R[n];
    rep(i, n) scanf("%lld%lld", &L[i], &R[i]);
    sort(L, L+n, greater<>());
    sort(R, R+n);
    lint ans = 0, tmp = 0;
    rep(i, n){
        chmax(ans, tmp + L[i]);
        chmax(ans, tmp - R[i]);
        chmax(ans, tmp + L[i] - R[i]);
        tmp += L[i] - R[i];
    }
    printf("%lld\n", ans * 2);
}

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

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

typedef long long int ll;

const ll INF=(ll)1e18;
//const int INF=(1<<30);

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 {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=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 {
    mint res(*this);
    return res/=a;
  }
};

mint mpow(int x, int n){
  if(n==0)return 1;

  mint y = mpow(x, n/2);
  y *= y;

  if(n%2==1) y *=x;
  return y;
}

mint combi(int n, int a){

  mint x = 1, y = 1;
  REP(i,a){
    x *= n-i;
    y *= i+1;
  }
  return x/y;
}

int main(){
  int n,a,b;

  cin >> n >> a >> b;

  mint ans = mpow(2,n) - 1;

  ans -= combi(n,a);
  ans -= combi(n,b);
  cout << ans.x << endl;
}



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

int arr[100000];
int main() {
    int n,k;
    cin >> n >> k;
    for (int i = 0; i<n; i++) {
        int height;
        cin >> height;
        arr[i] = height;
    }

    int total = 0;
    for ( int i=0; i<n; i++) {
        if (arr[i] >= k) {
            total ++;
        }
    }
    cout << total << "\n";
    return 0;
}

Measured memory_bytes: 640
from collections import deque

n = int(input())
g = []
# ans = [[-1]*n for _ in range(n)]
ans = [-1] * n
done = set()
q = deque()

for i in range(n):
    temp = list(map(int, input().split()))
    g.append(temp[2:])

# print(g)

q.append(0)
# dis = 1
ans[0] = 0
done.add(1)

while q:
    idx = q.popleft()
    adj = g[idx]
    # print('node:', idx+1)

    for i in adj:
        if i not in done:
            ans[i-1] = ans[idx] + 1
            done.add(i)
            q.append(i-1)
    # if len(adj) > 0:
    #     dis += 1

# print(ans)

for i in range(n):
    print(i+1, ans[i])


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

struct Point{double x,y;};
bool comp(Point a,Point b) {return (a.x==b.x ? a.y<b.y : a.x<b.x);}
double dist(Point a,Point b) {return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}

bool Intersection(Point p1,Point p2,Point p3,Point p4,Point *ret){
    double d = (p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x);
    double u = ((p3.x-p1.x)*(p4.y-p3.y)-(p3.y-p1.y)*(p4.x-p3.x))/d;
    double v = ((p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x))/d;
    if(d==0 || u<=0 || u>=1 || v<=0 || v>=1)return false;
    ret->x = p1.x+u*(p2.x-p1.x);
    ret->y = p1.y+u*(p2.y-p1.y);
    return true;
}

int main(void){
    int n;
    while(cin>>n,n){
    	int division=1;
        vector<Point> p1(n);
        vector<Point> p2(n);
    	rep(i,n){
            cin>>p1[i].x>>p1[i].y>>p2[i].x>>p2[i].y;
            vector<Point> cross;
            rep(j,i){
                Point ret;
                if(Intersection(p1[i],p2[i],p1[j],p2[j],&ret)){
                    cross.push_back(ret);
                }
            }
            sort(cross.begin(),cross.end(),comp);
            int cnt=1;
            if(cross.size()==0)cnt=0;
            for(int j=0;j+1<cross.size();j++){
                cnt+=(dist(cross[j],cross[j+1])>=eps);
            }
            division += cnt+1;
        }
        cout<<division<<endl;
    }

    return 0;
}

Measured memory_bytes: 1260
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import heapq
def prim_heap(n, edges):  # n: 最大の頂点番号+1, edges[頂点番号]=[[重み, 行き先],[重み, 行き先],...]. 無向グラフの場合は相方向有向グラフの表記にしておく。
    seen = [False] * n #True:不使用
    edgelist = []  # heapq
    for e in edges[0]:  # 頂点 0 から伸びる辺をすべて heapq に入れる。
        heapq.heappush(edgelist,e)
    seen[0] = True  # 頂点 0 は見たと記録する。
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)  # edgelist から最小の辺を1つ取り出す。
        if seen[minedge[1]]:  # その辺の行き先がすでに見た先だったら棄却して次へ。
            continue
        v = minedge[1]  # 行き先を v とする。
        seen[v] = True  # 頂点 v は見たと記録する。
        for e in edges[v]:  # 頂点 v から伸びる辺すべてについて、もしその行き先を見ていなかったら heapq に追加する。
            if not seen[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]  # いま使った辺の重みを結果に加える。
    return res  # 最小全域木の全体の重みを出力する。



def main(): 
    N = II()
    pos_li = []
    for i in range(N):
        x,y = LI()
        pos_li.append((x,y,i))
    edges = [[] for _ in range(N)]
    # # すべての頂点を結ぶグラフを作ってその最小全域木を取ると、時間が足りない（二重ループが O(10^10)）。
    # for i in range(N):
    #     for j in range(N):
    #         weight = min(abs(pos_li[i][0] - pos_li[j][0]), abs(pos_li[i][1] - pos_li[j][1]))
    #         edges[i].append([weight, j])
    #         edges[j].append([weight, i])
    # # なので、座標でソートして、最も近い4点のみへ辺を伸ばす。
    pos_li.sort(key=lambda x: x[0])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(x1-x2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    pos_li.sort(key=lambda x: x[1])
    for k in range(N-1):
        x1, y1, p1 = pos_li[k]
        x2, y2, p2 = pos_li[k+1]
        weight = abs(y1-y2)
        edges[p1].append([weight, p2])
        edges[p2].append([weight, p1])

    # print(edges)
    print(prim_heap(N, edges))


main()

Measured memory_bytes: 78316
if isfile("mystdin.txt");mystdin=open("mystdin.txt","r");redirect_stdin(mystdin);end
pI(x)=parse(Int,x)
pM(x::Array{SubString{String},1})=map(pI,x)
function main()
  x1,y1,x2,y2=pM(split(readline()))
  dx=x2-x1
  dy=y2-y1
  println(x2-dy," ",y2+dx," ",x1-dy," ",y1+dx)
end
main()
if isdefined(Base, :mystdin);close(mystdin);end

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

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

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

#define CHMIN(a, b) (a) = min((a), (b))
#define CHMAX(a, b) (a) = max((a), (b))

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()


int main() {
    string s;
    cin >> s;

    int tmp0=0;
    int tmp1=0;
    REP(i,s.length()){ 
        if(i%2==0&&s[i]=='1')tmp0++;
        if(i%2==1&&s[i]=='0')tmp0++;
        //0からスタート

        if(i%2==0&&s[i]=='0')tmp1++;
        if(i%2==1&&s[i]=='1')tmp1++;
        //1からスタート
    }


    cout << min(tmp0,tmp1) << endl;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
 
 
int mod = 1000000007;
long long dp[5010][5010];
 
int main(){
    vector<int> mov;
    int N,K,M,Q;
    cin >> N >> M >> K >> Q;
    for(int i = 0 ; i < N ; i++){
        if( (i / K) % 2 == 0 ){
			mov.push_back(i);
            //cerr << i << endl;
        }
    }
    dp[0][0] = 1;
    for(int i = 0 ; i <= 5000 ; i++){
		int tot[5010] = {};
		
		// for(int k = 0 ; k < N ; k++){
			// printf("%3d",dp[i][k]);
			// cout << " ";
		// }
		// cout << endl;
		// for(int k = 0 ; k < N ; k++) cout << (k/K%2==0?"  ^":"   ") << " ";
		// cout << endl;
		
		for(int k = 0 ; k < mov.size() ; k++){
			tot[0] += dp[i][mov[k]%N];
			tot[0] %= mod;
		}
		
		for(int j = 1 ; j < 2*K ; j++){
			tot[j] = tot[j-1];
			int c = -1;
			for(int k = 0 ; k < N ; k += K){
				tot[j] += c*dp[i][(k+j-1)%N];
				tot[j] %= mod;
				c *= -1;
			}
		}
		
		//reverse(tot,tot+2*K);
		// for(int j = 0 ; j < 2*K ; j++) cout << tot[j] << " " ;
		// cout << endl;
		
		for(int j = 0 ; j < N ; j++){
			dp[i+1][j] += tot[(K+1+j)%(2*K)];
			dp[i+1][j] %= mod;
		}
    }
    for(int i = 0 ; i < Q ; i++){
        int a,b,c;
        cin >> a >> b >> c;
        int d = ((c-a)%N+N)%N;
        cout << (dp[b][d]%mod+mod)%mod << endl;
    }
	// for(int i = 0 ; i < 15 ; i++){
		// for(int j = 0 ; j < 15 ; j++){
			// printf("%10d ",(dp[i][j]+mod)%mod);
		// }
		// cout << endl;
	// }
     
}

Measured memory_bytes: 197012
unittest
{
	assert( [ "2 7" ].solve == 4 );
	assert( [ "1 1" ].solve == 0 );
	assert( [ "50 4321098765432109" ].solve == 2160549382716056 );
}



import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto x = 0L;
	input.front.formattedRead!"%s %s"( n, x );
	
	auto ps = new long[ 1 + n ];
	auto bs = new long[ 1 + n ];
	ps[ 0 ] = 1;
	foreach( i; 0L .. n )
	{
		ps[ i + 1 ] = ps[ i ] * 2 + 1;
		bs[ i + 1 ] = bs[ i ] * 2 + 2;
	}
	
	return solve2( ps, bs, n, x );
}

auto solve2( long[] ps, long[] bs, long n, ref long x )
{
	auto t = 0L;
	if( ps[ n ] + bs[ n ] <= x )
	{
		t += ps[ n ];
		x -= ps[ n ] + bs[ n ];
	}
	else
	{
		if( x == 0 ) return t;
		x--;
		if( x == 0 ) return t;
		t += solve2( ps, bs, n - 1, x );
		if( x == 0 ) return t;
		t++;
		x--;
		if( x == 0 ) return t;
		t += solve2( ps, bs, n - 1, x );
		if( x == 0 ) return t;
		x--;
	}
	return t;
}


Measured memory_bytes: 2864
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
dist = 0
for x1, y1 in xy:
  for x2, y2 in xy:
    dist += ((x1-x2)**2 + (y1-y2)**2)**(1/2)
print(dist/n)

Measured memory_bytes: 3060