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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll N;
pll G[100005];
bool U[100];

ll solve(ll p, ll q)
{
    ll s = 0;
    memset(U, 0, sizeof(U));
    REP(i, N)
    {
        if (U[i])
            continue;
        s++;
        U[i] = true;
        int n = i;
        FOR(j, N, i + 1)
        {
            if (U[j])
                continue;
            if (G[j].first - p == G[n].first && G[j].second - q == G[n].second)
            {
                U[j] = true;
                n = j;
            }
        }
    }
    return s;
}

int main()
{
    cin >> N;
    REP(i, N)
    {
        cin >> G[i].first >> G[i].second;
    }
    sort(G, G + N, [](pll a, pll b) { return a.first == b.first ? a.second < b.second : a.first < b.first; });
    ll ans = N;
    REP(i, N)
    {
        REP(j, N)
        {
            if (i == j)
                continue;

            ll p = G[i].first - G[j].first;
            ll q = G[i].second - G[j].second;
            if (p == 0 && q == 0)
                continue;

            ll s = solve(p, q);
            ans = std::min(ans, s);
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <numeric>

int main()
{
	std::vector<std::vector<int>> input;
	std::vector<int> height_width(2);

	std::cin >> height_width[0] >> height_width[1];
	
	while (height_width[0] != 0 || height_width[1] != 0)
	{
		input.push_back(height_width);
		std::cin >> height_width[0] >> height_width[1];
	}

	size_t size = input.size();
	for (size_t i = 0; i < size; i++)
	{
		for (int j = 0; j < input[i][0]; j++)
		{
			for (int k = 0; k < input[i][1]; k++)
			{
				if ((j + k) % 2 == 0)
				{
					std::cout << "#";
				}
				else
				{
					std::cout << ".";
				}
			}
			std::cout << std::endl;
		}
	std::cout << std::endl;
	}
	return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/24  Problem: 006_agc_b / Link: https://agc006.contest.atcoder.jp/tasks/agc006_b?lang=en  ----- */
/* ------問題------

N 段のピラミッドがあります。 段は上から順に 1, 2, …, N と番号が振られています。 各 1≤i≤N について、i 段目には 2i−1 個のブロックが横一列に並んでいます。 また、各段の中央のブロックに注目すると、これらは縦一列に並んでいます。
すぬけ君は N 段目のブロックに (1, 2, …, 2N−1) を並べ替えたもの（順列）を書き込みました。 さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。
あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。
その後、すぬけ君はすべてのブロックに書き込まれた整数を消してしまいました。 すぬけ君は、1 段目のブロックに書き込まれた整数が x であったことだけを覚えています。
N 段目のブロックに書き込まれた順列としてあり得るものが存在するか判定し、存在するならばひとつ求めてください。

-----問題ここまで----- */
/* -----解説等-----

Xが2回連続する部分を作り出せればよい。1indexでX-1,X番目にXをつくる。
これによって頂点はXとなる。
これにはXを最下部の中央にしこれの周りをMin,Maxで囲めば良い。
また正当性はN>=5で成り立つことを示せればよい。
書くとわかる。(は？)

----解説ここまで---- */

LL N, X;

LL ans = 0LL;

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

	cin >> N >> X;

	if (X == 1 || X == 2 * N - 1) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
		VI a(2 * N - 1);
		FOR(i, 0, SZ(a))a[i] = i + 1;
		swap(a[N - 1], a[X - 1]);
		swap(a[0], a[N - 2]);
		swap(a[2 * N-2], a[N]);

		FOR(i, 0, SZ(a)) {
			cout << a[i] << endl;
		}

	}
	return 0;
}


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

int main() {
  
  int N;
  cin >> N;
  
  int counter = 36;
  
  for (int i = 0; i < N; i++) {
    
    int A; 
    cin >> A;
    
    int x = 0;
    
    while (A % 2 == 0) {
      x++;
      A /= 2;
    }
    
    if (x < counter) counter = x;
  
  }
  
  cout << counter << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int d[n];
  for(int i=0;i<n;i++)cin>>d[i];
  int num[110]={0};
  for(int i=0;i<n;i++){
    num[d[i]]++;
  }
   int res = 0;  // 答えを格納
    for (int i = 1; i <= 100; ++i) {  // 1 <= d[i] <= 100 なので 1 から 100 まで探索
        if (num[i]) {  // 0 より大きかったら
            ++res;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
h, w = map(int,input().split())
A = [input() for i in range(h)]

# print(A)

def a():
    c = -1
    for i in range(len(A)):
        c += A[i].count("#")
    
    s = [0, 0]
    while s != [h-1, w-1]:
        # print(s)
        if s[1]+1 < w and A[s[0]][s[1]+1] == "#":
            s[1] += 1
            c -= 1
        elif s[0]+1 < h and A[s[0]+1][s[1]] == "#":
            s[0] += 1
            c -= 1
        else:
            return "Impossible"
    if c == 0:
        return "Possible"
    else:
        return "Impossible"

print(a())

Measured memory_bytes: 38384
using System;

namespace aoj
{
    public class Knapsack
    {
        
        public static void Main()
        {
            // 入力処理
            string[] input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var W = int.Parse(input[1]);
            int[] values = new int[N];
            int[] weights = new int[N];
            for (var i = 0; i < N; ++i)
            {
                input = Console.ReadLine().Split(' ');
                values[i] = int.Parse(input[0]);
                weights[i] = int.Parse(input[1]);
            }

            // DPの生成
            int[][] dp = new int[N + 1][];
            for (var i = 0; i < N + 1; ++i) { dp[i] = new int[W + 1]; }
            // DPの初期化
            for (var w = 0; w <= W; ++w) { dp[0][w] = 0; }
            
            for (var i = 0; i < N; ++i)
            {
                for (var w = 0; w <= W; ++w)
                {
                    if (0 <= w - weights[i])
                    {
                        dp[i + 1][w] = Max<int>(dp[i][w - weights[i]] + values[i], dp[i][w]);
                    }
                    else
                    {
                        dp[i + 1][w] = dp[i][w];
                    }
                }
            }

            Console.WriteLine(dp[N][W]);
        }

        public static T Max<T>(T _a, T _b) where T : IComparable
        {
            return (_a.CompareTo(_b) < 0) ? _b : _a;
        }
    }
}



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

int main(){
    int n, ans, a, b; cin >> n >> ans;
    a =  ans;
    for(int i = 0; i < n-2; i++){
        cin >> b;
        ans += min(a, b);
        a = b;
    }
    cout << ans+a << endl;
    return 0;
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 0;
	for(int a = 1; a <= n; a++) {
		for(int b = 1;  a * b < n; b++) {
			if(a * b < n) ans++; 		
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3652
import bisect
from itertools import product

N, K = map(int, input().split())
D = map(int, input().split())
like_num = set(range(0,10)) ^ set(D)
length = len(str(N))

for l in range(length, length+2):
  comb = [int("".join(map(str, a))) for a in product(like_num, repeat=l)]
  ind = bisect.bisect_left(comb, N)
  if len(comb) != ind and comb[ind] >= N:
    print(comb[ind])
    exit()


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


int main(){
    int n;
    cin >> n;
    vector <int> vec(n);
    for ( int i = 0; i < n ; i++){
        cin >> vec.at(i);
    }
    int count = 0;
    sort(vec.begin(),vec.end());
    count = vec.at( (n / 2)  ) - vec.at ( n / 2 - 1);
    cout << count << endl;
}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 19 10:03:26 2017

@author: kotania
"""
from collections import Counter

N = int(input())
 
AList = []
 
for n in range(0,N):
    AList.append(input())
    
countDict = Counter(AList)
countDictValues = countDict.values()

count = 0

for c in countDictValues:
    if c % 2 == 1 :
        count += 1

print(count)

Measured memory_bytes: 19756
MOD = 10**9 + 7

N, M, K = map(int, input().split())

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

comb = getComb(N*M-2, K-2, MOD)

ans = 0
for i in range(N):
    ans += i*(N-i)*M*M
    ans %= MOD

for j in range(M):
    ans += j*(M-j)*N*N
    ans %= MOD

ans *= comb
ans %= MOD

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int t;
	cin>>t;
	string s;
	cin>>s;
	int ans=1;
	for(int i=0;i<s.size()-1;++i){
		if(s[i]!=s[i+1]) ++ans;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int i,j;
int N;
int M;
cin >> N >> M;
int A,B,C;
priority_queue<int> q;
pair<int,int> CB[M];
for(i=0;i<N;i++){
  cin >> A;
  q.push(A);}
for(i=0;i<M;i++){
  cin >> B >> C;
  CB[i]=make_pair(C,B);}
sort(CB,CB+M);
int count = 0;
for(j=M-1;j>=0;j--){
  tie(C,B)=CB[j];
  while(B!=0){
    q.push(C);
    B--;
    count++;
    if(count>=N)break;
  }
  if(count>=N)break;
}
long long int ans = 0;
for(i=0;i<N;i++){
    ans += q.top();
    q.pop();
 }
 cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2168
//organize and stay in moment
//Abhinav - IIITA
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int32_t main(){
	int n,w; cin>>n>>w;
	int we[n],val[n];
	bool poss[100005];
    int wei[100005];
	for(int i=0;i<n;++i)
		cin>>we[i]>>val[i];
	for(int i=0;i<100005;++i)
	{
	    wei[i]=LLONG_MAX;
	    poss[i]=false;
	}
	poss[0]=true;
	wei[0]=0;
	for(int i=0;i<n;++i){
		for(int j=100004;j>=0;--j){ 
			if(j<val[i])
				break;
			if(poss[j-val[i]]){
				poss[j]=true;
				wei[j]=min(wei[j],wei[j-val[i]]+we[i]);
			}
		}
	}
	for(int j=100004;j>=0;--j){
		if(poss[j] && wei[j]<=w){
			cout<<j;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <map>
const int MOD = 1e9+7;
using namespace std;

int ctoi(char c){
	return c - '0';
}


int main(){
	string s;
	long long dp[1000000][2];
	cin >> s;
	reverse(s.begin(), s.end());

	dp[0][0] = ctoi(s[0]);
	dp[0][1] = 10 - ctoi(s[0]);
	for (int i = 1; i < s.length(); i++){
		dp[i][0] = min(dp[i-1][0] + ctoi(s[i]), dp[i-1][1] + ctoi(s[i]) + 1);
		dp[i][1] = min(dp[i-1][0] + 10 - ctoi(s[i]), dp[i-1][1] + 9 - ctoi(s[i]));
	}

	cout << min(dp[s.length()-1][0], dp[s.length()-1][1] + 1) << endl;
	return 0;
}

Measured memory_bytes: 17028
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int ans=1;
	for(int i=1;i<n;i++){
		if(s[i]!=s[i-1]) ans++;
	}
	cout<<ans<<'\n';
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

const int mod = 1e9+7;

string L;
int dp[100010][2];

int rec(int digit, int smaller) {
	if (digit >= L.size()) {
		return dp[digit][smaller] = 1;
	}

	if (dp[digit][smaller] != -1) {
		return dp[digit][smaller];
	}

	int ret = 0;
	int d = L[digit] - '0';
	
	if (smaller == 0) {
		if (d == 1) {
			ret += rec(digit+1, 0)*2;
			ret %= mod;
			ret += rec(digit+1, 1);
			ret %= mod;
		} else {
			ret += rec(digit+1, 0);
			ret %= mod;
		}
	} else {
		ret += rec(digit+1, 1)*3;
		ret %= mod;
	}

	return dp[digit][smaller] = ret;
}

signed main() {
	cin >> L;
// int dp[100010][2];
	rep (i, 100010) rep (j, 2) dp[i][j] = -1;
	int ans = rec(0, 0);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6656
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] S = new boolean[14];
		boolean[] H = new boolean[14];
		boolean[] C = new boolean[14];
		boolean[] D = new boolean[14];
		String suit;
		int cardNum;
		
		for (int i = 0; i < n; i++){
			suit = sc.next();
			cardNum = sc.nextInt();
			if (suit.equals("S")){S[cardNum] = true;}
			if (suit.equals("H")){H[cardNum] = true;}
			if (suit.equals("C")){C[cardNum] = true;}
			if (suit.equals("D")){D[cardNum] = true;}
		}
		
		printCards("S", S);
		printCards("H", H);
		printCards("C", C);
		printCards("D", D);
	}
	
	static void printCards(String suit, boolean[] cards){
		for (int i = 1; i <= 13; i++){
			if (!(cards[i])){
				System.out.println(suit + " " + i);
			}
		}
	}
}

Measured memory_bytes: 18048
n, c, k = map(int, input().split())
times = sorted([int(input()) for _ in range(n)])

count = 0
passengers = 0
border = 0
for i in range(n):
    if border == 0:
        border = times[i] + k
    if c > passengers and border >= times[i]:
        passengers += 1
        if passengers == c:
            count += 1
            passengers = 0
            border = 0
    elif border < times[i]:
        count += 1
        passengers = 1
        border = times[i] + k

print(count + 1 if passengers > 0 else count)

Measured memory_bytes: 8280
#include <iomanip>
#include <cmath>
#include <functional>
#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int x[n], y[n];
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    function<double(double, double)> f = [&](double p, double q) {
        double maxd2 = 0;
        for (int i = 0; i < n; i++) {
            double dx = p - x[i], dy = q - y[i];
            maxd2 = max(maxd2, dx * dx + dy * dy);
        }
        return sqrt(maxd2);
    };
    function<double(double)> g = [&](double p) {
        double ly = -2000, ry = 2000, ans;
        for (int j = 0; j < 100; j++) {
            double y1 = (2 * ly + ry) / 3, y2 = (ly + 2 * ry) / 3,
                f1 = f(p, y1), f2 = f(p, y2);
            if (f1 < f2) ry = y2; else ly = y1;
            ans = f1;
        }
        return ans;
    };
    double lx = -2000, rx = 2000, ans;
    for (int i = 0; i < 100; i++) {
        double x1 = (2 * lx + rx) / 3, x2 = (lx + 2 * rx) / 3,
            g1 = g(x1), g2 = g(x2);
        if (g1 < g2) rx = x2; else lx = x1;
        ans = g1;
    }
    cout << setprecision(12) << ans << endl;
}


Measured memory_bytes: 256
from sys import stdin


def f(s, p, P, i):
    # 再帰
    # 順にスイッチを見ていく
    if len(s) == i:
        return 1 if P == p else 0
    # 場合の数
    # そのスイッチを使用しなかった場合 + 使用した場合
    return f(s, p, P, i + 1) + f(s, p, P ^ s[i], i + 1)


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
    pn = (int(i) for i in lines[-1].split())
    # s[スイッチID]
    # 二進法で表した数における各桁はそのスイッチを使用している電球
    s = [0] * N
    for i in range(M):
        for j in sn[i]:
            s[j - 1] |= (1 << i)
    # p
    # 二進法で表した数における各桁は電球
    # MOD 2 におけるゼロイチをそのまま2進数とする
    p = 0
    for i, j in enumerate(pn):
        p |= (1 << i) if j == 1 else 0
    print(f(s, p, 0, 0))


main()


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		//????????£?????????????????????
		Scanner sc = new Scanner(System.in);
		String str ="";
		//??°?????????
		while(true){
			//???????????????????????????
			str = sc.next(); 
			//"-"????????????????????????
			if(str.equals("-")){
				break;
			}
			//??°????????????
			int num = sc.nextInt();
			
			//??????????????°???????????£?????????
			for(int i = 0;i< num;i++){
				int h = sc.nextInt();
				//
				str = str.substring(h)+str.substring(0,h);
			}
			//??¨???
			System.out.println(str);
		}
	}
}

Measured memory_bytes: 26288
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		int a = N;
		int b = 1;
		string ans = "No";
		while(true){
			a -= b;
			if(a==0){
				ans = "Yes";
				b += 1;
				break;
			} else if(a<0){
				break;
			} else {
				b += 1;
			}
		}
		Console.WriteLine(ans);
		if(ans == "Yes"){
		List<int>[] C = new List<int>[b];
		for(var i=0;i<b;i++){
			C[i] = new List<int>();
		}
		int a1 = 0;
		int ia = 0;
		while(true){
			for(var j=ia+1;j<b;j++){
				C[ia].Add(a1+1);
				C[j].Add(a1+1);
				a1 += 1;
			}
			ia += 1;
			if(a1==N){
				break;
			}
		}
		Console.WriteLine(b);
		for(var i=0;i<b;i++){
			Console.Write(C[i].Count);
			for(var j=0;j<C[i].Count;j++){
				Console.Write(" "+C[i][j]);
			}
			Console.WriteLine();
		}
		}
	}
}

Measured memory_bytes: 17472
#include <stdio.h>
#include <string.h>

//int fish[1000001];

int main(void)
{
	int *fish;
	int n, q;
	int a, v;
	int winner;
	int i, j;
	
	fish = (int *)calloc(1000001, sizeof(int));
	
	scanf("%d%d", &n, &q);
	
	winner = 1;
	for (i = 0; i < q; i++){
		scanf("%d%d", &a, &v);
		fish[a] += v;
		if (a == winner){
			if (v < 0){
				winner = 1;
				for (j = 2; j <= n; j++){
					if (fish[winner] < fish[j]){
						winner = j;
					}
				}
			}
		}
		else {
			if ((fish[winner] == fish[a]) && (a < winner)){
				winner = a;
			}
			else if (fish[winner] < fish[a]){
				winner = a;
			}
		}
		printf("%d %d\n", winner, fish[winner]);
	}
	
	return (0);
}

	
	



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

int main(){
  int X,res;
  cin >> X;
  if(X<600){
    res = 8;
  }else if(X<800){
    res = 7;
  }else if(X<1000){
    res = 6;
  }else if(X<1200){
    res = 5;
  }else if(X<1400){
    res = 4;
  }else if(X<1600){
    res = 3;
  }else if(X<1800){
    res = 2;
  }else if(X<2000){
    res = 1;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(void){
	long long a,b,i,x=0,c=0;
	scanf("%lld %lld",&a,&b);
	while(1){
		c++; x=a*c;
		if(x%b==0){
			printf("%lld\n",x);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1728
n, k = map(int, raw_input().split())
p = [map(int, raw_input().split()) for i in range(n)]
p = sorted(p, key=lambda _: _[0])
ans = 10**30
for b in range(n):
    x_b, y_b = p[b]
    for t in range(n):
        x_t, y_t = p[t]
        if y_t <= y_b:
            continue
        v = filter(lambda _: y_b <= _[1] <= y_t, p)
        for i in range(len(v) - k + 1):
            x_i, y_i = v[i]
            x_j, y_j = v[i+k-1]
            ans = min(ans, (x_j - x_i) * (y_t - y_b))
print ans


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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  vector<pair<int,int>> num;
  int to_wh = 0, to_bk = 0;
  for (int i = 0; i < N; ++i) {
    S[i] == '#' ? to_wh++ : to_bk++;
    num.push_back({to_wh, to_bk});
  }
  
  // for (auto&& e : num) cout << e.first << ' ' << e.second << endl;

  int all_wh = num[N-1].second;
  vector<int> chng;
  chng.push_back(all_wh);
  for (int i = 0; i < N; ++i) {
    chng.push_back(all_wh + num[i].first - num[i].second);
  }
  
  // for (auto&& e : chng) cout << e << ' ';
  
  cout << endl << *min_element(chng.begin(), chng.end()) << endl;
}

Measured memory_bytes: 3828
#include <stdio.h>

int main(void)
{
	char s[1001],t[1001];
	int nos,not,i,j,same,ans=1001;
	scanf("%s%s",&s,&t);
	nos = strlen(s);
	not = strlen(t);
	for(i=0;i<=nos-not;i++){
		same = 0;
		for(j=0;j<not;j++){
			if(s[j+i]!=t[j]) same++;
		}
		if(ans>same) ans = same;
	}
	printf("%d",ans);
	return 0;
}

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

#define STRING(str) #str

template <typename T >
void print_vec_1d(vector<T> x, string name) {
	cout << name << endl;
	cout << "[ ";
	for (int i=0;i<x.size();i++) {
		cout << x[i];
		if (i != x.size()-1) cout << ", ";
		else cout << " ]" << endl;
	}
}

int main() {
	int x;
	cin >> x;
	cout << ((x==1)?0:1) << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>

using namespace std;

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


  std::cin >> r >> d >> x;

  for (int i = 0; i < 10; i++) {
    x = r*x - d;
    std::cout << x << std::endl;
  }

  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
// int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n) cin >> a[i];
  
  int sum =0;
  rep(i,n) sum+=a[i];
  sum/=n;
  
  ll res1 = 0;
  rep(i,n) res1+=pow(sum-a[i],2);
  sum++;
  ll res2 = 0;
  rep(i,n) res2+=pow(sum-a[i],2);
  
  cout << min(res1,res2) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
    map<pair<int, int>, int> M;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            auto p = make_pair(X[i] - X[j], Y[i] - Y[j]);
            if (p.first == 0 && p.second < 0) p.second *= -1;
            if (p.first < 0) p.first *= -1, p.second *= -1;
            M[p]++;
        }
    }
    int nmax = 0;
    for (auto p : M) {
        nmax = max(nmax, p.second);
    }
    cout << N - nmax << '\n';
    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919LL
#define MOD 1000000007

int N, M;
int A[1000][1000];
long long F[1000][1000][31];
long long K[1000];

long long f(int i, int pos, long long k) {
  //if (k <= 30 || pos > 12) return F[i][pos][min(k, 30LL)];
  if (k == 0 || pos > 12) return F[i][pos][min(k, 30LL)];
  long long s = A[i][pos], p = 1;
  long long n = k, r = 1;
  for (int x=pos-1; x>=0; x--) {
    assert((p*n)%r == 0);
    p = (p*n)/r;
    n++, r++;
    s += 1LL*p*A[i][x];
    if (p >= INF || s >= INF) return INF;
  }
  if (k <= 30) assert(s == F[i][pos][k]);
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  rep(i, N) rep(j, M) cin >> A[i][j];
  rep(i, N-1) if (A[i][0] > A[i+1][0]) {
    cout << -1 << "\n";
    return 0;
  }
  if (M == 1) {
    //assert(false);
    bool ok = true;
    rep(i, N-1) if (A[i][0] >= A[i+1][0]) ok = false;
    cout << (ok?0:-1) << "\n";
    return 0;
  }
  rep(i, N) {
    rep(j, M) F[i][j][0] = A[i][j];
    rep(f, 30) rep(j, M) F[i][j][f+1] = min(F[i][j][f] + (j>0?F[i][j-1][f+1]:0), INF);
  }
  rep(i, N-1) {
    if (A[i][0] != A[i+1][0]) continue;
    int a = A[i][0];
    long long cur_sec = 1LL*K[i]*A[i][0]+A[i][1];
    if (A[i+1][1] < cur_sec) {
      long long X = (cur_sec-A[i+1][1]+a-1)/a;
      K[i+1] += X;
    }
    if (cur_sec == 1LL*K[i+1]*A[i+1][0]+A[i+1][1]) {
      // if a[i] >= a[i+1]: do +1
      bool ord = false;
      for (int pos=2; pos<M; pos++) {
        long long k1 = K[i], k2 = K[i+1];
        long long a = -1, b = -1;
        if (k1 <= k2) {
          // <=> A[i]^0[pos] < A[i+1]^(k2-k1)[pos]
          a = A[i][pos];
          b = f(i+1, pos, k2-k1);
        }
        else {
          // <=> A[i]^(k1-k2)[pos] < A[i+1]^0[pos]
          a = f(i, pos, k1-k2);
          b = A[i+1][pos];
        }
        if (a < b) {
          ord = true;
          break;
        }
        if (a > b) break;
      }
      //cout<<"i="<<i<<"-"<<i+1<<": ord="<<ord<<"\n";
      if (!ord) K[i+1]++;
    }
  }
  /*
  rep(i, N) {
    rep(j, M) cout <<f(i, j, K[i])<<",";cout<<"\n";
  }
  */
  long long m = 0;
  rep(i, N) m += K[i];
  cout << m << "\n";
  return 0;
}


Measured memory_bytes: 246400
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
int main()
{
  long N, P;
  cin >> N >> P;
  map<long, long> mp;
  for (long i = 2; i * i <= P; i++)
  {
    while (P % i == 0)
    {
      mp[i]++;
      P /= i;
    }
  }
  if (P != 1)
    mp[P]++;
  long ans = 1;
  for (auto m : mp)
  {
    ans *= pow(m.first, m.second / N);
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
	std::vector<int> v;

	for (size_t i = 0; i < 10000; i++)
	{
		int temp;
		std::cin >> temp;
		v.push_back(temp);
	}

	for (size_t i = 0; i < v.size(); i++)
	{
		std::cout << "Case " << i + 1 << ": " << v[i] << std::endl;
	}
    return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */


int main() {
  ll n,a,b; cin >> n >> a >> b;
  cout << min(a*n, b) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

ll mod = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();
	
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	vector<int> b(m);
	vector<int> cnt(1000010);
	rep(i, n) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	rep(i, m) {
		cin >> b[i];
		cnt[b[i]]++;
	}
	sort(all(a)); sort(all(b));
	rep(i, n - 1) {
		if (a[i] == a[i + 1]) {
			cout << 0 << endl;
			return 0;
		}
	}
	rep(i, m - 1) {
		if (b[i] == b[i + 1]) {
			cout << 0 << endl;
			return 0;
		}
	}
	int no = 0;
	int ans = 1;
	for (int i = n * m; i >= 1; i--) {
		if (cnt[i] == 1) {
			if (binary_search(all(a), i)) {
				int tmp = m - (upper_bound(all(b), i) - b.begin());
				ans *= tmp;
				ans %= mod;
			}
			else {
				int tmp = n - (upper_bound(all(a), i) - a.begin());
				ans *= tmp;
				ans %= mod;
			}
		}
		else if (cnt[i] == 0) {
			int tmp = (m - (upper_bound(all(b), i) - b.begin()))* (n - (upper_bound(all(a), i) - a.begin()));
			tmp -= n * m - i;
			ans *= tmp;
			ans %= mod;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<string>v;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		v.push_back(s);
	}
	vector<string>::iterator ip; 
  
    int count; 
    sort(v.begin(), v.end()); 
 
    count = std::distance(v.begin(), 
                          std::unique(v.begin(), v.begin() + n)); 
  
  
    cout<< count; 
  
    return 0; 
} 

Measured memory_bytes: 11636
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

bool graph[50][50];
bool visited[8];

int dfs(int a, int n, bool visited[]){
  bool all_visited = true;
  fr(i,n) if(visited[i] == false) all_visited = false;
  
  if(all_visited) return 1;
  int ret = 0;
  fr(i, n) {
    if(visited[i]) continue;
    if(graph[a][i] == true){
      visited[i] = true;
      ret += dfs(i, n, visited);
//      visited[i] = false;
    }
  }  
 // if(graph[1][2] == false) cout << ret << endl;
  return ret;
}

int main(void) {
  int n,m;cin>>n>>m;
  fr(i, m) {
    int a,b;cin>>a>>b;
    a--;b--;
    graph[a][b] = graph[b][a] = true;
  }
  int ans = 0;
  fr(i,n) fr(j,n){
    if(i>j) continue;
    bool visited[50];

    if(graph[i][j] == true) {
      graph[i][j] = graph[j][i] = false;
 //     cout << dfs(0, n, visited) << "aaaa" << endl;
      int t = 0;
      fr(l, n) {
        fr(k, n) visited[k] = false;
        visited[l] = true;
        t += dfs(l, n, visited);
      }
      if (t == 0) ans++;
 //     cout << i << " " << j << endl;
    //  cout << ans << endl;
      graph[i][j] = graph[j][i] = true;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
s_arr = readlines.map(&:chomp)

sorted = {}
cnt= 0
n.times do |i|
    now = s_arr[i].chars.sort.join
    if sorted[now] == nil
        sorted[now] = 1
    else
        cnt += sorted[now]
        sorted[now] += 1
    end
end
p cnt

Measured memory_bytes: 38404
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
k = int(readline())

X = [[i for i in range(1, 10)]]
for i in range(9):
    Y = []
    for x in X[-1]:
        s = x % 10
        if s == 0:
            Y.append(x*10+s)
            Y.append(x*10+s+1)
        elif s == 9:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
        else:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
            Y.append(x*10+s+1)
    X.append(Y)

XX = []
for x in X:
    XX += x[:]
#XX = sorted(XX)

print(XX[k-1])

Measured memory_bytes: 14244
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1<<17;

int main(){
    int d,w;
    while(cin >> d >> w){
        if(d==0&&w==0) break;
        int st[d][w];
        for(int i=0;i<d;i++){
            for(int j=0;j<w;j++){
                cin >> st[i][j];
            }
        }
        int ans=0;
        for(int i=0;i<d;i++){
            for(int j=0;j<w;j++){
                for(int y=3;y<=d;y++){
                    for(int x=3;x<=w;x++){
                        int mini=INF,maxi=-1;
                        if(d<i+y||w<j+x) continue;
                        int sum=0;
                        for(int s=0;s<y;s++){
                            for(int t=0;t<x;t++){
                                if(s==0||s==y-1||t==0||t==x-1){
                                    mini=min(mini,st[i+s][j+t]);
                                }
                                else{
                                    sum+=st[i+s][j+t];
                                    maxi=max(maxi,st[i+s][j+t]);
                                }
                            }
                        }
                    if(maxi<mini) ans=max(ans,mini*(x-2)*(y-2)-sum);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3008
import java.util.*;
 
class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] b = new int[n];
    int a = 0;
    b[0] = 10000;
    boolean trig = true;
    int j = 0;
    long money = 1000;
    long kabu = 0;
    
    for (int i=0; i<n; i++){
      a = sc.nextInt();
      if (trig && b[j]>=a) {
        b[j] = a;
      } else if (trig) {
        trig = false;
        j++;
        b[j] = a;
      } else if (!trig && b[j]<=a) {
        b[j] = a;
      } else {
        trig = true;
        j++;
        b[j] = a;
      }
    }
        
    for (int i=0; i<=j; i++){
      if (i%2 == 1){
        money = money + kabu * b[i];
        kabu = 0;
      } else {
        kabu = money / b[i];
        money = money % b[i];
      }
    }
    
	System.out.println((money + kabu*b[j]));
    sc.close();
  }
}

Measured memory_bytes: 35968
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P;
typedef priority_queue<int> Pr;
int const MOD = 1000000007;
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(){
    cin.tie(0); ios::sync_with_stdio(false);

    int n,ans=1e5; string s; cin>>n>>s; int w[n+1]={},b[n+1]={};
    for (int i = 0; i < n; i++){
        if(s[i]=='.'){w[i+1]=w[i]+1; b[i+1]=b[i];}
        else {w[i+1]=w[i]; b[i+1]=b[i]+1;}
    }
    for (int i = 0; i <= n; i++){
        chmin(ans,w[n]-w[i]+b[i]);
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 2196
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {

  ll K;
  cin >> K;
  vector<bool> check(K, false);
  ll seven = 7;
  ll ans = 1;
  while (true) {
    if (seven % K == 0) break;
    else {
      ans++;
      seven %= K;
      if (check[seven]) {
        cout << -1 << endl;
        return 0;
      }
      check[seven] = true;
      seven = seven * 10 + 7;
    }
  }

  cout << ans << endl;
      
  return 0;
}

Measured memory_bytes: 3744
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<numeric>

using namespace std;

int main(){
  int n;cin>>n;
  if(n%2) cout<<(n*2)<<endl;
  else cout<<n<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
typedef long long ll;
typedef pair<int, int> P;

int n;
int ans = 0;

bool check(ll x) {
    bool a = false, b = false, c = false;
    while (1) {
        if (a && b && c) break;
        int y = x%10;
        if (y == 3) a = true;
        if (y == 5) b = true;
        if (y == 7) c = true;
        if (x < 10) break;
        x /= 10;
    }
    return a&&b&&c;
}

void dfs(ll x) {
    if (x > n) return;
    if (check(x)) ans++;
    dfs(10*x+3);
    dfs(10*x+5);
    dfs(10*x+7);
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
}

Measured memory_bytes: 256
function Main(s){
  var n = +s;
  var ans = 0;
  for(var i = 1; i <= n; i += 2){
    var f = 0;
    for(var j = 1; j <= i; j++){
      if(i % j === 0)f++;
    }
    if(f === 8)ans++;
  }
  console.log(ans);
}

Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 7372
n=int(input())
V=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
	v=[int(j) for j in input().split(" ")]
	u=v.pop(0)
	k=v.pop(0)
	for j in range(k):
		V[u-1][v[j]-1]=1



for i in range(n):
	print(" ".join([str(j) for j in V[i]]))

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

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

const int MAXN = 1000;
const int MAXS = 10000;
ll dp[MAXN + 5][2 * MAXS + 5];
 
auto maxx(auto& a, auto b){a = max(a, b);}
void reorder(auto& v, const auto& mapping) {
  auto v2 = v;
  rep(i, 0, sz(v))
    v[i] = v2[mapping[i]];
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n;
  cin >> n;
  vi w(n), s(n), v(n);
  rep(i, 0, n)
    cin >> w[i] >> s[i] >> v[i];

  vi ind(n);
  iota(all(ind), 0);
  sort(all(ind), [&](int i, int j) {return s[i] + w[i] < s[j] + w[j];});
  reorder(v, ind), reorder(w, ind), reorder(s, ind);
  
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  rep(i, 0, n) {
    rep(weight, 0, MAXS + 1) {
      if (dp[i][weight] == -1) continue;
      maxx(dp[i + 1][weight], dp[i][weight]);
      if (weight <= s[i])
	maxx(dp[i + 1][weight + w[i]], dp[i][weight] + v[i]);
    }
  }
  auto res = 0LL;
  rep(i, 0, n + 1)
    maxx(res, *max_element(all(dp[i])));
  cout << res << '\n';
}


Measured memory_bytes: 157312
#include<iostream>
#include<string>
using namespace std;
string S[15] = { "Rock", "Fire", "Scissors", "Snake", "Human", "Tree", "Wolf", "Sponge", "Paper", "Air", "Water", "Dragon", "Devil", "Lightning", "Gun" };
int N, a[10000], c[15]; string T;
bool solve(int a, int b) {
	if (a > b)b += 15;
	if (b - a <= 7)return true;
	return false;
}
int main() {
	while (true) {
		cin >> N;
		if (N == 0)break;
		for (int i = 0; i < N; i++) {
			cin >> T;
			for (int j = 0; j < 15; j++) {
				if (T == S[j])a[i] = j;
			}
		}
		for (int i = 0; i < 15; i++)c[i] = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!solve(a[i], a[j]))goto E;
			}
			c[a[i]] = 1;
		E:;
		}
		int G = 0;
		for (int i = 0; i < N - 1; i++) {
			if (a[i] != a[i + 1])G = 1;
		}
		int P = 0;
		if (G == 0)goto F;
		for (int i = 0; i < 15; i++) {
			if (c[i] == 1) {
				P = 1; cout << S[i] << endl;
			}
		}
	F:;
		if (P == 0)cout << "Draw" << endl;
	}
	return 0;
}

Measured memory_bytes: 1220
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let a: Vec<u64> = sc.vec(1 << n);
    let mut top2 = vec![vec![]; 1 << n];
    for mask in 0..(1 << n) {
        top2[mask].push((a[mask], mask));
    }
    for mask in 0..(1 << n) {
        for i in 0..n {
            let next_mask = mask | (1 << i);
            let top2_mask = top2[mask].clone();
            top2[next_mask].extend(top2_mask);
            top2[next_mask].sort();
            top2[next_mask].dedup();
            top2[next_mask].reverse();
            if top2[next_mask].len() > 2 {
                top2[next_mask].resize(2, (0, 0));
            }
        }
    }

    let mut max = 0;
    for mask in 1..(1 << n) {
        let (a, _) = top2[mask][0];
        let (b, _) = top2[mask][1];
        max = cmp::max(max, a + b);
        println!("{}", max);
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 31740
N, M = map(int, input().split())

love = 0

for i in range(N):
  KA = input().split()
  love_i = 0
  for j in range(1, int(KA[0]) + 1):
    love_i += 2 ** (int(KA[j]) - 1)
  if i == 0:
    love += love_i
  else:
    love = love & love_i

love_bin_str = "{}".format(bin(love)).replace("0b", "")
print(love_bin_str.count("1"))

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

int main(){
  int N,t=0,M;
  cin>>N;
  vector<int> T(N);
  for(int &i:T){
    cin>>i;
    t+=i;
  }
  cin>>M;
  for(int i=0;i<M;i++){
    int P,X;
    cin>>P>>X;
    cout<<t+X-T[P-1]<<endl;
  }
}

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

public class Main {
    FastScanner in;
    PrintWriter out;

    void solve() {
        int n = in.nextInt();
        long[] a = new long[n + 1];
        long s = 0;
        for (int i = 0; i < n; i++) {
            s += in.nextInt();
            a[i] = s;
        }
        Arrays.sort(a);
        long res = 0;
        for (int i = 0; i < a.length; ) {
            int j = i;
            while (j != a.length && a[i] == a[j]) {
                j++;
            }
            long len = (j - i);
            res += len * (len - 1) / 2;
            i = j;
        }
        out.println(res);
    }

    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, a, b;
vector<int> ans;
vector<int> tmp;

void solveEven(int x) {
    int n = ans.size();
    if (n == 1) {
        ans.pb(x);
        return;
    }
    tmp.clear();
    forn(i, n - 2) {
        if (i & 1) {
            tmp.pb(ans[i] ^ x);
            tmp.pb(ans[i]);
        } else {
            tmp.pb(ans[i]);
            tmp.pb(ans[i] ^ x);
        }
    }
    tmp.pb(ans[n - 2]);
    tmp.pb(ans[n - 1]);
    tmp.pb(ans[n - 1] ^ x);
    tmp.pb(ans[n - 2] ^ x);
    ans = tmp;
}

void solveOdd(int x) {
    int n = ans.size();
    tmp.clear();
    forn(i, n) {
        if (i & 1) {
            tmp.pb(ans[i] ^ x);
            tmp.pb(ans[i]);
        } else {
            tmp.pb(ans[i]);
            tmp.pb(ans[i] ^ x);
        }
    }
    ans = tmp;
}

void deb() {
    for (int x : ans) {
        forn(i, n) printf("%d", (x >> i) & 1);
        printf(" ");
    }
    puts("");
}

int main() {
    cin >> n >> a >> b;
    b ^= a;
    int cnt = 0;
    forn(i, n) if (b & (1 << i)) {
         ++cnt;
    }
    if (cnt % 2 == 0) {
        cout << "NO" << endl;
        return 0;
    }
    printf("YES\n");
    bool odd = false;
    ans.pb(0);
//    deb();
    forn(i, n) if (b & (1 << i)) {
        if (odd) {
            solveOdd(1 << i);
        } else {
            solveEven(1 << i);
        }
        odd ^= 1;
//        deb();
    }
    forn(i, n) if (!(b & (1 << i))) {
        solveOdd(1 << i);
//        deb();
    }
    for (int x : ans) {
        printf("%d ", x ^ a);
    }
    puts("");
    return 0;
}


Measured memory_bytes: 2292
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    ll N,K;
    cin >> N >> K;
    N = N % K;
    cout << min(N,K - N) << endl;
}


Measured memory_bytes: 256