akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

import static java.lang.System.*;

class Main {
	public static Scanner sc = new Scanner(in);
	public static Random rand=new Random();

	public void run() {
		while(true){
			int n=sc.nextInt();
			if(n==0)break;

			int[] a=nextIntArray(n);
			Arrays.sort(a);
			int sum=0;
			for(int i=1;i<n-1;i++){
				sum+=a[i];
			}
			ln(sum/(n-2));
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

	public int[] nextIntArray(int n){
		int[] res=new int[n];
		for(int i=0;i<n;i++){
			res[i]=sc.nextInt();
		}
		return res;
	}
	public static void pr(Object o) {
		out.print(o);
	}
	public static void ln(Object o) {
		out.println(o);
	}
	public static void ln() {
		out.println();
	}
}

Measured memory_bytes: 21172
s,c=input(),int(input())
a=eval(s)
b=int(s[0])
for i in range(1,len(s),2):b=b+int(s[i+1]) if s[i]=='+' else b*int(s[i+1])
if(a==b==c):e='U'
elif(a==c):e='M'
elif(b==c):e='L'
else:e='I'
print(e)

Measured memory_bytes: 7708
#include <stdio.h>
#include <stdlib.h>
int n;
int main(void)
{
    scanf("%d", &n);
    int h[n + 1], i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &h[i]);
    }
    /* for (i = 1; i < n; i++)
    {
        if (h[i] < h[i - 1])
        {
            if (h[i - 1] - 1 != h[i])
            {
                printf("No");
                exit(0);
            }
        }
    }*/
    for (i = 0; i < n - 1; i++)
    {
        if (h[i] <= h[i + 1])
        {
            if (h[i + 1] - h[i] >= 1)
            {
                h[i + 1] -= 1;
            }
        }
        else
        {
            printf("No");
            exit(0);
        }
    }

    printf("Yes");
    return 0;
}

Measured memory_bytes: 512
#include <cstdio>
int ans[] = {4,4,9,4,7,10,18,5,21,8,16,11,11,19,19,6,14,22,22,9,9,17,17,12,25,12,113,20,20,20,108,7,28,15,15,23,23,23,36,10,111,10,31,18,18,18,106,13,26,26,26,13,13,114,114,21,34,21,34,21,21,109,109,8,29,29,29,16,16,16,104,24,117,24,16,24,24,37,37,11,24,112,112,11,11,32,32,19,32,19,94,19,19,107,107,14,120,27,27,27};
int main(){
	int s;scanf("%d",&s);printf("%d\n",ans[s-1]);
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n, k;

		n = sc.nextInt();
		k = sc.nextInt();
		if (n % k == 0) {
			System.out.println(0);
		} else {
			System.out.println(1);
		}

		sc.close();
	}

}


Measured memory_bytes: 22740
main :: IO ()
main = do
  _ <- getLine
  as <- map read . words <$> getLine
  print $ counter as

counter
  :: [Int] -> Int
counter ns = helper ns 0

helper
  :: [Int] -> Int -> Int
helper ms k
  | all even ms = helper (map (`div` 2) ms) $! (k+1)
  | otherwise   = k

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<pair<int, int>, int> PP;
const ll INF = 1LL << 60;
const int MAX = 1000000000;
const ll MOD = 1000000007;

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }
//------------------------------------------------------------------------------------------------------------------------------

struct Edge {
    int to, id;
};
vector<vector<Edge>> G;
vector<int> ans;

void dfs(int v, int c = -1, int p = -1) {
    int k = 1;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i].to;
        int ei = G[v][i].id;
        if (u == p) {
            continue;
        }
        if (k == c) {
            k++;
        }
        ans[ei] = k;
        k++;
        dfs(u, ans[ei], v);
    }
}
int main(void) {
    int N;
    cin >> N;
    G.resize(N);
    ans.resize(N - 1);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back((Edge){b, i});
        G[b].push_back((Edge){a, i});
    }

    dfs(0);

    int mx = 0;
    for (int i = 0; i < N; i++) {
        mx = max(mx, (int)G[i].size());
    }
    cout << mx << endl;
    for (int i = 0; i < N - 1; i++) {
        cout << ans[i] << endl;
    }
}

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

int main(){
	int N;
	cin >> N;
	
	int ans = 1;
	rep(i,3){
		ans *= N;
	}
	
	cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  double a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  rep(i,n) {
    a[0]=(a[0]+a[i])/2;
  }
  pd(a[0]);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
 
total_a = sum(a_list)
#約数の列挙
candidates = set()
for i in range(1, total_a):
    if i * i > total_a:
        break
    if total_a % i == 0:
        candidates.add(i)
        candidates.add(total_a // i)        
ans = 1
for x in candidates:
    remainders = sorted(map(lambda a: a % x, a_list))
    total_r = sum(remainders)    
    border = total_r // x
    need = sum(remainders[:(N - border)])
    
    # print(x, remainders, total_r, border, need)
    if need <= K:
        ans = max(ans, x)
print(ans)

Measured memory_bytes: 3064
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())#縦と横の大きさを入力から得る
maze = "".join(input() for _ in range(H))#入力を全行数分取得
#配列を生成する。np.zeros()は全てを0に初期化する関数
#第１引数は H*W,H*Wの２次元配列、第２引数はbool型を意味する
array = np.zeros((H * W, H * W), dtype=np.bool)

for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)#divmod()は商と余りを求める関数。（r:商　c:余り）

    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
        array[n - 1][n] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
        array[n - W][n] = 1
dist = csgraph.shortest_path(array)
print(int(dist[dist < 401].max()))
    

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

#define INF 100100100
#define MOD 1000000007

using namespace std;
using ll = long long;
using ull = unsigned long long ;

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

   ll n;
   cin>>n;
   vector<ll>a(n);
   for(ll i=0;i<n;i++)cin>>a[i];
   vector<ll>ans(2*n+1);
   int right = n+1;
   int left = n-1;
   ans[n] = a[0];
   if(n%2){
      for(ll i=1;i<n;i++){
         if(i%2){
            ans[right++] = a[i];
         }
         else{
            ans[left--] = a[i];
         }
      }
   }
   else{
      for(ll i=1;i<n;i++){
         if(i%2){
            ans[left--] = a[i];
         }
         else{
            ans[right++] = a[i];
         }
      }
   }

   for(ll i=left+1;i<right-1;i++)cout<<ans[i]<<" ";
   cout<<ans[right-1]<<endl;
   return 0;
}


Measured memory_bytes: 6912
use std::io;

fn main() {
    let mut buf1 = String::new();
    let mut buf2 = String::new();
    io::stdin().read_line(&mut buf1).ok();
    let S = buf1.trim();
    io::stdin().read_line(&mut buf2).ok();
    let T = buf2.trim();

    let mut ans = 0;
    for i in 0..3 {
        if S.chars().nth(i).unwrap() == T.chars().nth(i).unwrap() {
            ans += 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 2160
import sys
from io import StringIO
import unittest


def input():
    return sys.stdin.readline().rstrip()


def resolve():
    N = int(input())
    S = input()

    R = S[0]
    for i in range(1, N):
        if S[i] != R[-1]:
            R += S[i]
    print(len(R))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """10
aabbbbaaca"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
aaaaa"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """20
xxzaffeeeeddfkkkkllq"""
        output = """10"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 5868
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdint>

typedef std::map<std::string, std::uint32_t> OccurenceWordMap;

class compare_second {
		typedef OccurenceWordMap::value_type value_type;
	public:
		bool operator()(value_type const& lhs, value_type const& rhs) const
		{
			return lhs.second < rhs.second;
		}
};

class compare_length {
		typedef std::string value_type;
	public:
		bool operator()(value_type const& lhs, value_type const& rhs) const
		{
			return lhs.length() < rhs.length();
		}
};

int main()
{
	std::string input_text;
	std::getline(std::cin, input_text);
	typedef std::vector<std::string> StringVec;
	StringVec word_vec;
	std::string::size_type pos1 = 0;
	std::string::size_type pos2;
	while ((pos2 = input_text.find(' ', pos1)) != std::string::npos) {
		word_vec.push_back(input_text.substr(pos1, pos2 - pos1));
		pos1 = pos2 + 1;
	}
	word_vec.push_back(input_text.substr(pos1, input_text.size() - pos1));
	OccurenceWordMap ow_map;
	for (std::string const& word : word_vec) {
		auto i = ow_map.lower_bound(word);
		if (i != ow_map.end() && !(ow_map.key_comp()(word, i->first))) {
			++i->second;
		}
		else {
			ow_map.insert(std::make_pair(word, 0));
		}
	}
	std::cout << std::max_element(ow_map.begin(), ow_map.end(), compare_second())->first << ' '
			  << *std::max_element(word_vec.begin(), word_vec.end(),  compare_length()) << std::endl;
	return 0;
}

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

int main(){
  int a, b;
  cin >> a >> b;
  if((a+b)%2==0){
    cout << (a+b)/2;
  }
  else{
    cout << (a+b)/2+1;
  }
  cout << endl;
  return 0;
}

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

typedef long long ll;
const int MAX = 2e5 + 5;
const int K = 21;
ll ar[MAX];
int n;
ll dp[MAX];
ll sum[MAX];
int cnt[K];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> ar[i];
    int start = 0;
    int end = 0;
    bool ok = true;
    ll sum = 0;
    ll xor_sum = 0;
    ll ans = 0;
    while (end < n){
        sum += ar[end];
        xor_sum ^= ar[end];
        if (sum == xor_sum){
            ans += (end - start + 1);
        } else{
            while (sum != xor_sum){
                sum -= ar[start];
                xor_sum ^= ar[start];
                start += 1;
            }
            ans += (end - start + 1);
        }
        end += 1;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 5200
#include<stdio.h>
int main()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(b<c||d<a) printf("0");
	else 
	{
		if(a<c) a=c;
		if(b>d) b=d;
		int sum=b-a;
		printf("%d",sum);
	}
}

Measured memory_bytes: 128
# coding: utf-8
# Your code here!
import fractions

def isok(a,b,c,d):
    if a < b or b > d:
        print('No')
        return
    g= fractions.gcd(d, b)
    r=((c-a%g)//g)*g+a%g
#    print(r)
    if r+g-b < 0:
        print('No')
    else:
        print('Yes')
    

T=int(input())

for _ in range(T):
    a,b,c,d = list(map(int,input().split()))
    isok(a,b,c,d)



Measured memory_bytes: 5688
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(int i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
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 <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;



int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k, q; cin >> k >> q;
    vector<int> d(k); rep (i, k) cin >> d[i];
    rep (_, q) {
        int n, x, m; cin >> n >> x >> m;
        ll ans = 0;
        x %= m;
        vector<int> dd = d; rep (i, k) dd[i] %= m;
        ll sum = x; rep (i, k) sum += (ll)dd[i % k] * ((i < (n - 1) % k ? 1 : 0) + ((n - 1) / k));
        ans += (sum / m);
        eprintf("%lld\n", sum / m);
        rep (i, k) {
            ans += (dd[i] == 0 ? 1 : 0) * ((i < (n - 1) % k ? 1 : 0) + ((n - 1) / k));
            eprintf("%d %d %d %d\n",(dd[i] == 0 ? 1 : 0), (((i < (n - 1) % k) ? 1 : 0)), ((n - 1) / k), (dd[i] == 0 ? 1 : 0) * ((i < (n - 1) % k ? 1 : 0) + ((n - 1) / k)));
        }
        cout << n - 1 - ans << "\n";
    }
    return 0;
}

Measured memory_bytes: 384
def count(array)
  cnt = 0
  return cnt if array.empty? || array.all? {|t| t == 0 }

  while array.all? {|t| t > 0 }
    array = array.map {|e| e -= 1 }
    cnt += 1
  end

  split = array.index(0)
  len = array.length

  if split == 0
    cnt += count(array[1..len - 1])
  else
    cnt += count(array[0..(split - 1)]) + count(array[(split + 1)..(len - 1)])
  end

  cnt
end

n = gets.chomp.to_i
h = gets.chomp.split.map(&:to_i)

puts count(h)

Measured memory_bytes: 1788
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int id;
	int time_s;
	int time_cs;
	int chosen;
} sensyu_t;

int qsort_comp(const void* x,const void* y) {
	const sensyu_t* a=(const sensyu_t*)x;
	const sensyu_t* b=(const sensyu_t*)y;
	if((a->time_s)>(b->time_s))return 1;
	if((a->time_s)<(b->time_s))return -1;
	if((a->time_cs)>(b->time_cs))return 1;
	if((a->time_cs)<(b->time_cs))return -1;
	return 0;
}


int main(void) {
	sensyu_t sensyu[24];
	int i;
	for(i=0;i<24;i++) {
		scanf("%d %d.%d",
			&sensyu[i].id,
			&sensyu[i].time_s,&sensyu[i].time_cs);
		sensyu[i].chosen=0;
	}
	qsort(&sensyu[0],8,sizeof(sensyu_t),qsort_comp);
	qsort(&sensyu[8],8,sizeof(sensyu_t),qsort_comp);
	qsort(&sensyu[16],8,sizeof(sensyu_t),qsort_comp);
	sensyu[0].chosen=sensyu[1].chosen=1;
	sensyu[8].chosen=sensyu[9].chosen=1;
	sensyu[16].chosen=sensyu[17].chosen=1;
	printf("%d %d.%02d\n",
		sensyu[0].id,sensyu[0].time_s,sensyu[0].time_cs);
	printf("%d %d.%02d\n",
		sensyu[1].id,sensyu[1].time_s,sensyu[1].time_cs);
	printf("%d %d.%02d\n",
		sensyu[8].id,sensyu[8].time_s,sensyu[8].time_cs);
	printf("%d %d.%02d\n",
		sensyu[9].id,sensyu[9].time_s,sensyu[9].time_cs);
	printf("%d %d.%02d\n",
		sensyu[16].id,sensyu[16].time_s,sensyu[16].time_cs);
	printf("%d %d.%02d\n",
		sensyu[17].id,sensyu[17].time_s,sensyu[17].time_cs);
	qsort(sensyu,24,sizeof(sensyu_t),qsort_comp);
	for(i=0;i<24;i++) {
		if(!sensyu[i].chosen) {
			printf("%d %d.%02d\n",
				sensyu[i].id,sensyu[i].time_s,sensyu[i].time_cs);
			break;
		}
	}
	for(i++;i<24;i++) {
		if(!sensyu[i].chosen) {
			printf("%d %d.%02d\n",
				sensyu[i].id,sensyu[i].time_s,sensyu[i].time_cs);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 0
N, X = map(int, input().split())
if X <= N:
    print(0)
    exit(0)
p = [0]*(N+1)
p[0] = 1
for i in range(1, N+1):
    p[i] = p[i-1]*2 + 3


def solve(N, X):
    ret = 0
    if X == p[N]:
        return((p[N]+1) // 2)
    elif X <= N:
        return(0)
    else:
        if X >= (p[N] + 1) // 2:
            ret += ((p[N-1]+1) // 2) + 1
            X = X - (p[N-1] + 1)
        ret += solve(N-1, X-1)
        return(ret)


print(solve(N, X))


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

int main() {
    int n, q; cin >> n >> q;
    dsu uf(n);
    while (q--) {
        int t; cin >> t;
        int u, v; cin >> u >> v;
        if (t == 0) {
            uf.merge(u, v);
        } else {
            cout << uf.same(u, v) << endl;
        }
    }
}

Measured memory_bytes: 4008
import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int n = Integer.parseInt(br.readLine());
    StringBuilder result = new StringBuilder();
    for (String s : process(n)){
      result.append(s).append("\n");
    }
    System.out.println(result);
  }
  
  public static List<String> process(int length){
    if (length == 1){
      List<String> result = new ArrayList<>();
      result.add("a");
      return  result;
    } else {
      List<String> result = new ArrayList<>();
      for (String s : process(length - 1)) {
        char append = 'a';
        int maxCodePoint = 0;
        for (char c : s.toCharArray()){
          if (maxCodePoint < c){
            maxCodePoint = c;
          }
        }
        while (append <= maxCodePoint+1) {
          result.add(s + append);
          append++;
        }
      }
      return result;
    }
  }
}


Measured memory_bytes: 52224
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define sz(x) int(x.size())

typedef long long ll;

using namespace std;

static const int MAX = 100001;

int main(int argc, const char * argv[]) {
    // input from txt
    /////////
    //write//
    /////////
    
    int n;
    int *h;
    h = new int[MAX];
    
    cin >> n;
    rep(i, n){
        cin >> h[i];
        if(i){
            if(h[i]>h[i-1])h[i]--;
        }
    }
    
    bool flag = true;
    rep(i, n){
        if(i ){
            if(h[i]<h[i-1]){
                flag = false;
                break;
            }
        }
    }
    
    if(flag)cout << "Yes";
    else cout << "No";
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long int n,a,b;
    cin>>n>>a>>b;
    if((n>1 && b>=a )|| (n==1 && a==b))
        cout<<(n-2)*(b-a)+1<<endl;
    else
        cout<<0<<endl; 
    return 0;
 } 

Measured memory_bytes: 256
#include <list>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

LL R, C, N;

struct rim
{
	LL x, y, id;
	int val;
	rim(LL xx, LL yy, LL idid)
		:x(xx), y(yy), id(idid)
	{
		val = value();
	}
	LL value()const
	{
		if (y == 0)return x;
		if (x == R)return R + y;
		if (y == C)return R + C + R - x;
		assert(x == 0);
		return R + C + R + C - y;
	}
};

int main(void)
{
	cin >> R >> C >> N;
	vector<rim>cash;
	for (int i = 0; i < N; ++i)
	{
		LL x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		bool fl1 = (x1 == 0 || x1 == R);
		bool fl2 = (y1 == 0 || y1 == C);
		bool fl3 = (x2 == 0 || x2 == R);
		bool fl4 = (y2 == 0 || y2 == C);
		if ((fl1 || fl2) && (fl3 || fl4))
		{
			cash.push_back(rim(x1, y1, i));
			cash.push_back(rim(x2, y2, i));
		}
	}
	sort(cash.begin(), cash.end(), [](const rim& c1, const rim&c2) 
	{
		return c1.value() < c2.value();
	});
	list<int>ids;
	for (auto& a : cash)
	{
		ids.push_back(a.id);
	}
	if (ids.empty())
	{
		cout << "YES\n";
		return 0;
	}
	auto lef = ids.begin();
	auto rht = lef;
	rht++;
	if (rht == ids.end())rht = ids.begin();
	for (int i = 0; i < 1e7; ++i)
	{
		while (*lef == *rht)
		{
			lef = ids.erase(lef);
			if (lef == ids.end())lef = ids.begin();
			lef = ids.erase(lef);
			if (lef == ids.end())lef = ids.begin();
			if (ids.empty())
			{
				cout << "YES\n";
				return 0;
			}
			rht = lef;
			if (lef == ids.begin())lef = ids.end();
			--lef;
		}
		lef++;
		rht++;
		if (lef == ids.end())lef = ids.begin();
		if (rht == ids.end())rht = ids.begin();
		if (ids.empty())
		{
			cout << "YES\n";
			return 0;
		}
	}
	cout << "NO\n";
	return 0;
}


Measured memory_bytes: 14696
//------------------------------------------
// C++ templete
//------------------------------------------
#include <bits/stdc++.h>
#define int long long
using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<VS> VVS;

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

//container util
//------------------------------------------
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define PRINT(V)     \
  for (auto v : (V)) \
  cout << v << " "
#define PRINTL(V)    \
  for (auto v : (V)) \
  cout << v << endl
#define SORT(V) sort((V).begin(), (V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//最大公約数
//------------------------------------------
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

//grobal variable
//------------------------------------------
int N, M;
VI Vec;

//main
//------------------------------------------
signed main()
{
  string s;
  cin >> s;
  if (s == "ARC"){
    cout << "ABC";
  }
  else{
    cout << "ARC";
  }
}

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

int main() {

  int n;
  cin >> n;
  
  n = n % 10;
  
  if (n==2||n==4||n==5||n==7||n==9) {
    cout << "hon" << endl;
  } else if (n==0||n==1||n==6||n==8) {
    cout << "pon" << endl;
  } else {
    cout << "bon" << endl;
  }
 
}


Measured memory_bytes: 3600
let N = Int(readLine()!)!
let A = [0] + readLine()!.characters.split(" ").map { Int(String($0))! }

var result = 0
for i in 0 ..< A.count {
    if i < A[i] && A[A[i]] == i {
        result += 1
    }
}
print(result)


Measured memory_bytes: 5824
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s=sc.next();
if((s.charAt(0)==s.charAt(1)&&s.charAt(1)==s.charAt(2))||(s.charAt(1)==s.charAt(2)&&s.charAt(2)==s.charAt(3))){System.out.println("Yes");}else{
System.out.println("No");}
}}

Measured memory_bytes: 23764
#include <iostream>
using namespace std;
typedef pair<int, int> P;
int main(void){
    int h, w, n, y, x;
    string s, t;
    cin>>h>>w>>n>>y>>x>>s>>t;
    int a=x, b=x, c=y, d=y;
    for(int i=0;i<n;i++){
        if(s[i]=='R')a++;
        if(s[i]=='L')b--;
        if(s[i]=='D')c++;
        if(s[i]=='U')d--;
        if(a>w||b<1||c>h||d<1){
            cout<<"NO"<<endl;
            return 0;
        }
        if(t[i]=='L')a=max(1, a-1);
        if(t[i]=='R')b=min(w, b+1);
        if(t[i]=='U')c=max(1, c-1);
        if(t[i]=='D')d=min(h, d+1);
    }
    cout<<"YES"<<endl;
}


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

#define MAXLENGTH 200
int main(void)
{
  int i,j,a=0;
  char s[MAXLENGTH],p[MAXLENGTH];

  scanf("%s",s);
  scanf("%s",p);

  sprintf(s,"%s%s",s,s);
  
  for(j=0;j<strlen(s);j++)
    {
      if(s[j]==p[0])
	{
	  for(i=0;i<strlen(p);i++)
	    {
	      if(p[i]!=s[j+i])
		break;
	    }
	  if(i==strlen(p))
	    {
	      printf("Yes\n");
	      break;
	    }
	}
      
      if(j==strlen(s)-1)
	printf("No\n");
    }
  
}




Measured memory_bytes: 2140
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]

LIS = [a[-1]]
for i in range(n - 2, -1, -1):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_right(LIS, a[i])] = a[i]

print(len(LIS))

Measured memory_bytes: 56024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    double ans = 0.0;
    REP (i, 1, n + 1) {
        int t = 0, w = i;
        while (w < k) {
            t++;
            w *= 2;
        }
        ans += 1.0 / n / (1 << t);
    }
    cout << fixed << setprecision(15) << ans << endl;

    return 0;
}


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

int main()
{
    int n; cin >> n;
    vector<int> l(n);
    for (int i = 0; i < n; i++) cin >> l[i];
    sort(l.begin(), l.end());
    ll ans = 0;
    for (int a = 0; a < n-2; a++) {
        for (int b = a+1; b < n-1; b++) {
            auto it = lower_bound(l.begin(), l.end(), l[a]+l[b]);
            if (it <= l.begin()+b) continue;
            ans += (it - (l.begin() + b + 1));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }

int main() {
   int H, W;
   cin >> H >> W;
   char f[H][W];
   int log1[H][W], log2[H][W];
   memset(log1, 0, sizeof(log1));
   memset(log2, 0, sizeof(log2));
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
         cin >> f[h][w];
      }
   }
   int cnt = 0;
   vector<int> log;
   for (int h = 0; h < H; h++) {
      cnt = 0;
      log.clear();
      for (int w = 0; w < W; w++) {
         if (f[h][w] == '#') {
            if (cnt > 0) {   
               log.push_back(cnt);
               cnt = 0;
            }
         } else {
            cnt++;
         }
      }
      if (cnt > 0) log.push_back(cnt);
      cnt = 0;
      if ((int)log.size() == 0) continue;
      int cnt2 = log[cnt];
      int in = cnt2;
      for (int w = 0; w < W; w++) {
         if (f[h][w] == '#') {
            log1[h][w] = 0;
         } else {
            log1[h][w] = in;
            cnt2--;
         }
         if (cnt2 == 0) {
            cnt++;
            cnt2 = log[cnt];
            in = cnt2;
         }
      }
   }
   for (int w = 0; w < W; w++) {
      cnt = 0;
      log.clear();
      for (int h = 0; h < H; h++) {
         if (f[h][w] == '#') {
            if (cnt > 0) {   
               log.push_back(cnt);
               cnt = 0;
            }
         } else {
            cnt++;
         }
      }
      if (cnt > 0) log.push_back(cnt);
      cnt = 0;
      if ((int)log.size() == 0) continue;
      int cnt2 = log[cnt];
      int in = cnt2;
      for (int h = 0; h < H; h++) {
         if (f[h][w] == '#') {
            log2[h][w] = 0;
         } else {
            log2[h][w] = in;
            cnt2--;
         }
         if (cnt2 == 0) {
            cnt++;
            cnt2 = log[cnt];
            in = cnt2;
         }
      }
   }
   /*
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
         cout << log1[h][w] << " ";
      }
      cout << endl;
   }
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
         cout << log2[h][w] << " ";
      }
      cout << endl;
   }
   */
   int ans = 0;
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
         if (f[h][w] == '.') ans = max(ans, log1[h][w] + log2[h][w] - 1);   
      }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 35456
#include <iostream>
#include<cstring>
#include<queue>

using namespace std;
void bfs();
typedef pair<int,int> p;
int w[4]={0,0,1,-1};
int s[4]={1,-1,0,0};
queue<p> que;
queue<p> que1;
const int maxn=1000+1;
char maze[maxn][maxn];
bool vis[maxn][maxn];
 int x,y;
 int num=0;
 void bfs1()
{
    while(que1.size())
    {

        p temp=que1.front();
        que1.pop();
        int nx=temp.first,ny=temp.second;
        for(int i=0;i<4;i++)
        {

            int sx=nx+w[i],sy=ny+s[i];
            if(sx>=0&&sx<x&&sy>=0&&sy<y&&maze[sx][sy]=='.')
               {

                maze[sx][sy]='#';
                que.push(p(sx,sy));
               }
        }
    }
    if(que.size()>0)
        {
            bfs();
            num++;
        }
    return ;


}
void bfs()
{
    while(que.size())
    {

        p temp=que.front();
        que.pop();
        int nx=temp.first,ny=temp.second;
        for(int i=0;i<4;i++)
        {

            int sx=nx+w[i],sy=ny+s[i];
            if(sx>=0&&sx<x&&sy>=0&&sy<y&&maze[sx][sy]=='.')
               {

                maze[sx][sy]='#';
                que1.push(p(sx,sy));
               }
        }
    }
    if(que1.size()>0)
    {
        bfs1();
        num++;

    }
    return ;

}

void check()
{

    for(int i=0;i<x;i++)
        for(int j=0;j<y;j++)
    {
        if(maze[i][j]=='#')
           {

           que.push(p(i,j));

           }
    }
}
bool pan()
{

     for(int i=0;i<x;i++)
        for(int j=0;j<y;j++)
         if(maze[i][j]=='.')
         return 0;
     return 1;
}
int main()
{


     while(cin>>x>>y)
     {  num=0;
          memset(vis,0,sizeof(vis));
         for(int i=0;i<x;i++)
            for(int j=0;j<y;j++)
            cin>>maze[i][j];
            check();
            bfs();
            cout<<num<<endl;

     }
     return 0;

}












Measured memory_bytes: 10384
N=int(input())
S=input()
r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
b = N - r - g

ans = r * g
ans = ans * b

for i in range( N ):
    for j in range(i+1, int((N+i)/2 +1 )):
        k = 2 * j - i
        if k < N:
            s = S[i] + S[j] + S[k]
            if ("R" in s) & ("G" in s) & ("B" in s):
                ans -= 1

print(ans)

Measured memory_bytes: 9188
import math

x = int(input())

if x == 2:
    print(2)
    exit()

while True:
    f = True
    g = math.ceil(math.sqrt(x))
    for i in range(2,g+1):
        if x%i == 0:
            f = False
            break
    if f == True:
        print(x)
        exit()
    x += 1

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;

int main(){
    string s;
    cin >> s;
    int c1 = 0;
    int c0 = 0;
    for (auto& c : s){
        if (c == '1') c1++;
        else c0++;
    }
    if (c0 > c1){
        cout << c1 * 2 << endl;
    }
    else{
        cout << c0 * 2 << endl;
    }

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, L;
  cin>>N>>L;

  Int a = 0;
  for(Int i=0;i<N;i++) a += L + (i+1) - 1;


  Int v = INF;
  Int ans = -1;
  for(Int i=0;i<N;i++){
    Int b = 0;
    for(Int j=0;j<N;j++) if(j != i) b += L + (j + 1) - 1;
    if(abs(a - b) < v) v = abs(a - b), ans = b;
  }
  
  cout<<ans<<endl;

  

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s, t;
	cin >> s;
	cin >> t;
	if (t.substr(0, t.length() - 1) == s)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

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

int main(){
	int n;
	cin >>n;
	int a[n];
	rep(i,n)cin>>a[i];
	sort(a,a+n);
	int asum=0,bsum=0;
	rep(i,n){
		if(i%2==1)asum+=a[i];
		else bsum+=a[i];
	}
	cout << abs(asum-bsum) << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N, Ma, Mb;
	cin >> N >> Ma >> Mb;
	int cnst = 4000;
	int dp[45][8005];
	for (int i = 0; i < 45; ++i) {
		for (int j = 0; j < 8005; ++j) {
			dp[i][j] = 1e9;
		}
	}
	for (int i = 0; i < N; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		int diff = a * Mb - b * Ma;
		dp[i + 1][cnst + diff] = min(dp[i + 1][cnst + diff],c);
		for (int j = 0;j<8005; ++j) {
			dp[i + 1][j] = min(dp[i+1][j],dp[i][j]);
			dp[i + 1][j + diff] = min(dp[i+1][j+diff],dp[i][j]+c);
		}
	}
	if (dp[N][cnst]<1e9) {
		cout << dp[N][cnst]<<endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 5044
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int x = scanner.nextInt();

        final int[] lengths = new int[n];

        for (int i = 0; i < lengths.length; i++) {
            lengths[i] = scanner.nextInt();
        }

        int i;
        int distance = 0;
        for (i = 0; i < n; i++) {
            distance += lengths[i];
            if (distance > x) {
                break;
            }
        }

        System.out.println(i + 1);
    }
}


Measured memory_bytes: 22868
#include<bits/stdc++.h>
typedef long long ll;
#define dbg          cout<<"Freak"<<endl;
#define dbgg(i)      cout<<i<<endl;
#define N            1e9+7
#define pb           push_back
using namespace std;
ll t;
ll arr[200005];
map<string,string>np;
vector<ll>v,v1;
int main()
{
    ll a,b,c,d,e,f=0,g,i,j,cnt;
    string s1,s2,s3;
    cin>>s1>>s2;
    cin>>a>>b;
    cin>>s3;
    if(s3==s1)a--;
    else b--;
    cout<<a<<' '<<b<<endl;

}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <bitset>
#include <cmath>
#include <ctime>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#include <chrono>
#include <functional>
#include <random>
#include <numeric>
#include <tuple>
#include <bitset>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef pair<int, int> ii;
template<class T> string toString(T x) { ostringstream ss; ss << x; return ss.str(); }
void solve();
int main() {
#ifdef LOCAL_COMP
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);
	solve();
#ifdef LOCAL_COMP
	cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int n, m;

bool ok(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < m;
}

vector<int> dsu;

int dsuFind(int x) {
	if (x == dsu[x]) return x;
	return dsu[x] = dsuFind(dsu[x]);
}

void dsuMerge(int x, int y) {
	x = dsuFind(x);
	y = dsuFind(y);
	dsu[x] = y;
}

void solve() {
	while (cin >> n >> m) {
		vector<string> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		dsu.resize(n * m);
		for (int i = 0; i < sz(dsu); i++) {
			dsu[i] = i;
		}
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < m; y++) {
				for (int s = 0; s < 4; s++) {
					int nx = x + dx[s];
					int ny = y + dy[s];
					if (ok(nx, ny)) {
						if (a[x][y] != a[nx][ny]) {
							dsuMerge(x * m + y, nx * m + ny);
						}
					}
				}
			}
		}
		map<int, int> w, b;
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < m; y++) {
				int v = x * m + y;
				v = dsuFind(v);
				if (a[x][y] == '#') {
					b[v]++;
				}
				else {
					w[v]++;
				}
			}
		}
		ll ans = 0;
		for (int i = 0; i < n * m; i++) {
			ans += ll(w[i]) * b[i];
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 16128
import sys
from fractions import gcd

input = sys.stdin.readline
A, B, C, D = map(int, input().split(' '))
num = B - A + 1
div_c = B // C - (A - 1) // C
div_d = B // D - (A - 1) // D
lcd = C * D // gcd(C, D)
div_cd = B // lcd - (A - 1) // lcd
print(num - div_c - div_d + div_cd)

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

int main(){
    int a,k;
    long long int sum=0;
    cin >> a >> k;
    int ar[a];
    for(int i=0; i<a; i++){
        scanf("%d",&ar[i]);
    }
    sort(ar,ar+a);
    for(int i=a-1; i>=0; i--){
        if(k==0)sum+=ar[i];
        else k--;
    }
    cout << sum <<endl;
    return 0;
}

Measured memory_bytes: 1024
cnt = 0
while True:
    cnt += 1
    maxweight = int(input())
    if maxweight == 0:
        break
    length = int(input())
    tresure = []
    dp = [[0 for n in range(length+1)] for m in range(maxweight + 1)]
    answeight = 0
    ansvalue = 0
    for l in range(length):
        v,w = (int(n) for n in input().split(","))
        tresure.append([v,w])
    for outer in range(length + 1):
        if outer == 0:
            continue
        weight = tresure[outer-1][1]
        value = tresure[outer-1][0]
        dp[weight][outer] = max(dp[weight][outer],value)
        for inner in range(maxweight + 1):
            if dp[inner][outer - 1] != 0:
                beforevalue = dp[inner][outer - 1]
                beforeweight = inner
                dp[inner][outer]  = max(beforevalue,dp[inner][outer])
                if beforeweight + weight <= maxweight:
                    nowvalue = dp[beforeweight + weight][outer]
                    dp[beforeweight + weight][outer] = max(nowvalue,beforevalue+value)
    #print(dp)
    for a in range(maxweight+1):
        #print(dp[a][length])
        if ansvalue < dp[a][length]:
            ansvalue = dp[a][length]
            answeight = a
    print("Case {0}:".format(cnt))
    print(ansvalue)
    print(answeight)

Measured memory_bytes: 19760
#include "bits/stdc++.h"

using namespace std;

void Main() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<int> C(N, 0);
    vector<vector<int> > A(N, vector<int>(M, 0));
    int minAmount = 0;
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        minAmount += C[i];
        for (int j = 0; j < M; ++j) {
            cin >> A[i][j];
        }
    }

    bool found = false;
    for (int b = 0; b < (1 << N); ++b) {
        bitset<12> bit(b);
        int tempC = 0;
        vector<int> tempX(M, 0);
        for (int i = 0; i < N; ++i) {
            if (bit.test(i)) {
                tempC += C[i];
                for (int j = 0; j < M; ++j) {
                    tempX[j] += A[i][j];
                }
            }
        }
        bool moreThanX = true;
        for (int j = 0; j < M; ++j) {
            if (tempX[j] < X) {
                moreThanX = false;
                break;
            }
        }
        if (moreThanX) {
            found = true;
            minAmount = min(minAmount, tempC);
        }
    }

    cout << (found ? minAmount : -1) << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3604
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		while(true){
			
			int n = sc.nextInt();
			int m = sc.nextInt();
			int a = sc.nextInt();
			
			if(n == 0 && m == 0 && a == 0){
				break;
			}
			
			int h[] = new int[m];
			int p[] = new int[m];
			int q[] = new int[m];
			int max = 0;
			
			for(int i = 0; i < m; i++){
				h[i] = sc.nextInt();
				p[i] = sc.nextInt();
				q[i] = sc.nextInt();
				if(h[i] > max){
					max = h[i];
				}
			}
			
			int map[][] = new int[n + 1][max + 1];
			
			for(int i = 0; i < n + 1; i++){
				for(int j = 0; j < max + 1; j++){
					map[i][j] = 0;
				}
			}
			
			for(int i = 0; i < m; i++){
				map[p[i]][h[i]] = q[i];
				map[q[i]][h[i]] = p[i];
			}
			
			int nowLocate[][] = new int[1][2];
			nowLocate[0][1] = max;
			nowLocate[0][0] = a;
			
			while(true){
				
				if(nowLocate[0][1] == 0){
					break;
				}
				if(map[nowLocate[0][0]][nowLocate[0][1]] != 0){
					nowLocate[0][0] = map[nowLocate[0][0]][nowLocate[0][1]];
				}
				nowLocate[0][1]--;
			}
			
			System.out.println(nowLocate[0][0]);
			
		}
		
	}

}

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

ll a, b, c, d;
map<ll, ll> rec;

ll dfs(ll n){
    if(n == 0) return 0;
    if(n == 1) return d;
    if(rec.count(n) > 0) return rec[n];
    ll mn = 1e18;
    if(n < mn/d) mn = n*d; // オーバーフロー対策
    ll l = (n/2) * 2;
    ll r = ((n+1)/2) * 2;
    mn = min(mn, (n-l)*d + a + dfs(l/2));
    mn = min(mn, (r-n)*d + a + dfs(r/2));
    l = (n/3) * 3;
    r = ((n+2)/3) * 3;
    mn = min(mn, (n-l)*d + b + dfs(l/3));
    mn = min(mn, (r-n)*d + b + dfs(r/3));
    l = (n/5) * 5;
    r = ((n+4)/5) * 5;
    mn = min(mn, (n-l)*d + c + dfs(l/5));
    mn = min(mn, (r-n)*d + c + dfs(r/5));
    rec[n] = mn;
    return mn;
}

int main(){
    ll T;
    cin >> T;
    rep(test, 0, T){
        rec.clear();
        ll n;
        cin >> n >> a >> b >> c >> d;
        cout << dfs(n) << endl;
    }
    return 0;
}

Measured memory_bytes: 4396
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string c[2];
  cin>>c[0]>>c[1];
  bool f=(c[0][0]==c[1][2])&&(c[0][1]==c[1][1])&&(c[0][2]==c[1][0]);
  cout<<(f?"YES":"NO")<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int ini[maxn], s[maxn];
int N, T, mx, ans;

int main()
{
	scanf("%d%d", &N, &T);
	for(int i = 1; i <= N; ++i) scanf("%d", &ini[i]);
	for(int i = N; i >= 1; --i) s[i] = max(s[i + 1], ini[i]);
	for(int i = 1; i < N; ++i) mx = max(mx, s[i + 1] -  ini[i]);
	for(int i = 1; i < N; ++i) if(s[i + 1] - ini[i] == mx) ans++;
	cout << ans;
	return 0;
}

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

struct edge{int to,cost;};
int ans[100010];
bool used[100010];
vector<edge> g[100010];

void dfs(int cur){
  used[cur] = true;
  for(int i = 0;i < g[cur].size();i++){
    edge e = g[cur].at(i);
    if(used[e.to] != true){
      if(e.cost % 2 == 0){
        ans[e.to] = ans[cur];
      }
      else{
        ans[e.to] = (ans[cur]+1)%2;
      }
      dfs(e.to);
    }
  }
  return;
}

int main(){
  int n;
  cin >> n;
  for(int i = 0;i < n-1;i++){
    int u,v,w;
    cin >> u >> v >> w;
    edge e;
    e.to = v;e.cost = w;
    edge f;
    f.to = u;f.cost = w;
    g[u].push_back(e);
    g[v].push_back(f);
  }
  ans[1] = 0;
  for(int i = 1;i <= n;i++){
    used[i] = false;
  }
  dfs(1);
  for(int i = 1;i <= n;i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
int n;
int a[200100];
bool chs[200100];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	int ccnt=0;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>=1;i--){
		int cnt=0;
		for(int j=i*2;j<=n;j+=i){
			cnt+=chs[j];
		}
		chs[i]=(a[i]-cnt+2)%2;
		ccnt+=chs[i];
	}
	bool flg=1;
	for(int i=1;i<=n;i++){
		int x=0;
		for(int j=i;j<=n;j+=i){
			if(chs[j])
				x++;
		}
		if(x%2!=a[i])
		{
			flg=0;
			break;
		}
	}
	if(flg){
		cout<<ccnt<<endl;
		for(int i=1;i<=n;i++)
			if(chs[i])
				cout<<i<<' ';
	}
	else{
		cout<<-1<<endl;
	}
	return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxH=10,mxW=1e3;
int h,w,k,ans=1e9;
string g[mxH];
vector<int> v[mxW];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>h>>w>>k;
	for(int i=0;i<h;++i)
	cin>>g[i];
	for(int i=0;i<1<<h-1;++i) 
	{
		int ca=__builtin_popcount(i);
		for(int j=0;j<w;++j) 
		{
			int s=0;
			for(int k=0;k<h;++k) 
			{
				s+=g[k][j]&1;
				if(i>>k&1) 
				{
					v[j].push_back(s);
					s=0;
				}
			}
			v[j].push_back(s);
			for(int vi : v[j])
			if(vi>k)
			ca=1e9;
		}
		vector<int> u(v[0].size());
		for(int j=0;j<w;++j) 
		{
			bool split=0;
			for(int l=0;l<u.size();++l)
			split|=u[l]+v[j][l]>k;
			if(split) 
			{
				++ca;
				u=vector<int>(u.size());
			}
			for(int l=0;l<u.size();++l)
			u[l]+=v[j][l];
			v[j].clear();
		}
		ans=min(ca,ans);
	}
	cout<<ans;
}

Measured memory_bytes: 384