akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
int dfs(vector<vector<int>> &adj, vector<int> &mark, int u, int counter)
{
	int result = 0;
	mark[u] = counter;
	for(int v : adj[u])
	{
		if (mark[v] == -1)
		{
			//cout << u << " : " << v << '\n';
			result += dfs(adj, mark, v, counter);
		}
	}
	return result + 1;
}
int main()
{
	SPEED
	int n, m, k, u, v;
	cin >> n >> m >> k;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; ++i)
	{
		cin >> u >> v;
		adj[u-1].pb(v-1);
		adj[v-1].pb(u-1);
	}

	vector<vector<int>> adj2(n);
	for (int i = 0; i < k; ++i)
	{
		cin >> u >> v;
		adj2[u-1].pb(v-1);
		adj2[v-1].pb(u-1);
	}

	vector<int> mark(n, -1);
	vector<int> count(n, 0);
	int counter = 0;

	//cout << "executed\n";

	for (int i = 0; i < n; ++i)
	{
		if (mark[i] != -1)
		{
			continue;
		}
		count[counter] = dfs(adj, mark, i, counter);
		//cout << "size : " << count[counter] << '\n';
		counter++;
	}
	for (int i = 0; i < n; ++i)
	{
		int t1 = 0;
		for (int u : adj[i])
		{
			if (mark[u]==mark[i])
			{
				t1++;
			}
		}

		for (int u : adj2[i])
		{
			if (mark[u]==mark[i])
			{
				t1++;
			}
		}

		cout << count[mark[i]] - 1 - t1 << " ";
	}
	return 0;
}

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

int main(){
	int n;
	int a;
	int b;
	int sum = 0;

	cin>>n>>a>>b;

	for(int i = 1; i <= n; i++){
		int res = 0;
		int j = i;
		while(j>0){
			res += j % 10;
			j  /= 10;
		}
		if(res >= a && res <= b) sum += i;
	}

	cout<<sum<<"\n";
	
}

	





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,W;
//long long dp[101][100001];
long long dp[100001];
int weigth[101];
int value[101];

int solve2() {
    int total = 0;
    for(int i=0;i<n;++i) {
        total += value[i];
    }
    for(int i=0;i<=total;++i)
        dp[i] = 2e9;
    dp[0] = 0;
    for(int i=0;i<n;++i)
        for(int v = total;v >= value[i];--v)
            dp[v] = min(dp[v], dp[v - value[i]] + weigth[i]);
    int ans = 0;
    for(int i=0;i<=total;++i)
        if(dp[i] <= W)
            ans = max(ans, i);
    return ans;
}
int main(int argc, char const *argv[]) {
    scanf("%d %d", &n, &W);
    for(int i=0;i<n;++i)
        scanf("%d %d", &weigth[i], &value[i]);
    printf("%d\n", solve2());

    return 0;
}

Measured memory_bytes: 4560
#include <stdio.h>
int main(void){
  int a[4]={0},i,lmt=3;
  for(i=1;i<=3;i++){
    scanf("%d",&a[i]);
  }
  for(i=1;i<=3;i++){
    if(a[i]==5) {lmt--;a[i]=0;break;}
}
  for(i=1;i<=3;i++){
    if(a[i]==7) {lmt--;a[i]=0;break;}
}
  for(i=1;i<=3;i++){
    if(a[i]==5) {lmt--;a[i]=0;break;}
}
  if(lmt==0) printf("YES");
  else printf("NO");
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();
            var c = 0;
            for (var i = 0; i < 3; i++)
            {
                if (s[i] == t[i]) c++;
            }

            Console.WriteLine(c);
        }

    }
}

Measured memory_bytes: 25848
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007LL;

int main(void) {
    int A, P;
    cin >> A >> P;
    cout << (A*3+P)/2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++)
class Cube{
    public:
    int f[6];
    Cube(){}
    void roll_y(){ roll(0, 2, 5, 3);}
    void roll_x(){ roll(0, 1, 5, 4);}
    void roll(int i, int j, int k, int l){
	int t = f[i]; f[i] = f[j]; f[j] = f[k]; f[k] = f[l]; f[l] = t;
    }
  
  bool valid(){
    bool v[6];
    rep(i, 6) v[i] = false;
    rep(i, 6) if ( 1 <= f[i]  && f[i] <= 6 ) v[f[i]-1] = true;
    rep(i, 6) if ( !v[i] ) return false;
    return f[0]+f[5]==7 && f[1]+f[4]==7 && f[2]+f[3]==7;
  }
};

class State{
  public:
  int pi, pj;
  Cube cube;
  State(){}
  State(int pi, int pj):pi(pi),pj(pj){
    rep(i, 6) cube.f[i] = -1;
  }
  bool operator < ( const State &s) const{
    if ( pi != s.pi ) return pi < s.pi;
    if ( pj != s.pj ) return pj < s.pj;
    rep(i, 6){
      if ( cube.f[i] == s.cube.f[i] ) continue;
      return cube.f[i] < s.cube.f[i];
    }
    return false;
  }
};

int G[7][7];
set<State> V;

bool dfs(State u){
  u.cube.f[5] = G[u.pi][u.pj];
  if ( u.cube.valid() ) return true;
  V.insert(u);

  State v;
  int di[4] = {1, -1, 0, 0};
  int dj[4] = {0, 0, -1, 1};
  int dp[4] = {1, 4, 3, 2};
  rep(r, 4){
    if ( u.cube.f[dp[r]] == -1 && G[u.pi+di[r]][u.pj+dj[r]] ||
	 u.cube.f[dp[r]] == G[u.pi+di[r]][u.pj+dj[r]] ){
      v = u;
      v.pi += di[r]; v.pj += dj[r];
      if ( dp[r] == 1 ) rep(i, 3) v.cube.roll_x();
      if ( dp[r] == 4 ) v.cube.roll_x();
      if ( dp[r] == 3 ) v.cube.roll_y();
      if ( dp[r] == 2 ) rep(i, 3) v.cube.roll_y();
      if ( V.find(v) == V.end() && dfs(v) ) return true;
    }
  }
  return false;
}

bool valid(vector<int> d){
  if ( d.size() != 6 ) return false;
  sort(d.begin(), d.end());
  rep(i, 6)
    if ( i+1 != d[i] ) return false;
  return true;
}

main(){
  int tcase; cin >> tcase;
  rep(t, tcase){
    rep(i, 7) rep(j, 7) G[i][j] = 0;
    int si, sj;
    vector<int> d;
    for ( int i = 1; i <= 5; i++ ){
      for ( int j = 1; j <= 5; j++ ){
	cin >> G[i][j];
	if ( G[i][j] ) { 
	  si = i; sj = j; 
	  d.push_back(G[i][j]);
	}
      }
    }
    State s = State(si, sj);
    V.clear();
    if ( valid(d) && dfs(s) ) cout << "true" << endl;
    else cout << "false" << endl;
  }
}



Measured memory_bytes: 3180
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class BinaryNode:
    def __init__(self, key, left=None, right=None):
        self.val = key
        self.left = left
        self.right = right


def insert(root, node):
    if root is None:
        root = node
    else:
        if root.val < node.val:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)
        else:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)


def preorder(root):
    ret = []
    if root is None: return ret
    ret.append(root.val)
    ret.extend(preorder(root.left))
    ret.extend(preorder(root.right))
    return ret


def inorder(root):
    ret = []
    if root is None: return ret
    ret.extend(inorder(root.left))
    ret.append(root.val)
    ret.extend(inorder(root.right))
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    s, key = sl()
    root = BinaryNode(int(key))

    for n in range(N - 1):
        input = sl()
        if input[0] == 'print':
            print("", *inorder(root))
            print("", *preorder(root))
        else:
            insert(root, BinaryNode(int(input[1])))


if __name__ == '__main__':
    main()



Measured memory_bytes: 121864
import copy
n,k = map(int,input().split())
r,s,p = map(int,input().split())
T = list(input())

for i in range(n-k):
    if T[i] == T[i+k]:
        T[i+k] = "x"
cr = T.count("r")
cp = T.count("p")
cs = T.count("s")
print(cp*s+cr*p+cs*r)



Measured memory_bytes: 4468
N, M = map(int, input().split(" "))
X = list(map(int, input().split(" ")))
X.sort()
total = X[-1]-X[0]
dif = [X[i+1] - X[i] for i in range(len(X)-1)]
dif.sort()
Y = [0 for i in range(N-1)]
for i in range(N-1):
  try:
    Y[i] = dif.pop()
  except:
    Y[i]=0
print(total-sum(Y))

Measured memory_bytes: 13960
N = int(input())
dp = [0] * 3

for i in range(N):
    a, b, c = map(int, input().split())
    x = max(dp[1] + a, dp[2] + a)
    y = max(dp[2] + b, dp[0] + b)
    z = max(dp[0] + c, dp[1] + c)
    dp = [x, y, z]

print(max(dp))


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

using namespace std;

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define rep(i, n) for(int i = 0; i < n; i++)
#define outl(x) cout<< (x) << '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

template<typename Tn> Tn gcd(Tn a, Tn b)
{
  return (b ? gcd(b, a % b) : a);
}

template<typename Tn> Tn lcm(Tn a, Tn b)
{
  return a / gcd(a, b) * b;
}

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

int n;
int a[100001];

llint solve(bool pm)
{
  llint cnt = 0;
  int sum = 0;
  rep(i, n) {
    if(pm && sum + a[i] > 0 || !pm && sum + a[i] < 0) {
      sum += a[i];
    } else {
      if(sum + a[i] == 0) cnt++;
      else cnt += abs(sum + a[i]) + 1;
      sum = pm ? 1 : -1;
    }
    pm = !pm;
  }

  return cnt;
}

int main()
{
  ci >> n;

  rep(i, n) ci >> a[i];

  co << min(solve(true), solve(false)) << en;
  
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;

const double PI = 3.1415926535;

double angle(double cur, double next){
    double r = cur - next + 2*PI;
    while( r >= 2*PI ) r -= 2*PI;
    return r;
}

int main(){
    int n;
    double x[100], y[100];
    while( scanf("%d", &n), n ){
        double cx = 10000, cy = 10000;
        int mem = 0;
        for(int i = 0; i < n; i++){
            scanf("%lf,%lf", x+i, y+i);
            if( x[i] < cx ){
                cx = x[i]; cy = y[i];
                mem = i;
            }
        }
        vector<bool> used(100, false);
        used[mem] = true;
        double cang = atan2(1, 0);
        double lv;
        int ln = mem;
        int i;
        for(i = 0; i < n; i++){
            lv = 100;
            int can = ln;
            for(int j = 0; j < n; j++){
                if( ln == j ) continue;
                double ang = angle( cang,
                                    atan2(y[j]-cy, x[j]-cx) );
                if( ang < lv ){
                    lv = ang; can = j;
                }
            }
            ln = can;
            cang = atan2(y[ln]-cy, x[ln]-cx);
            cx = x[ln]; cy = y[ln];
            if( used[ln] ) break;
            used[ln] = true;
        }
        printf("%d\n", n-i-1);
    }
    return 0;
}

Measured memory_bytes: 1140
#include <iostream>
#include<string>
int main()
{
	std::string S, T;
	std::string res = "Yes";
	std::cin >> S >> T;
	int i = 0;
	int j = 0;
	auto ite_S = S.begin();
	auto ite_T = T.begin();
	for (ite_S; ite_S != S.end(); ++ite_S, ++ite_T,i++,j++)
	{
		if ((int)S.find(*ite_S, i+1) != (int)T.find(*ite_T, j+1))
		{
			res = "No";
			std::cout << res << std::endl;
			return 0;
		}
		
	}
	std::cout << res << std::endl;
	return 0;
}

Measured memory_bytes: 776
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] p = new int[N];
		for(int i = 0; i < N; i++)
			p[i] = sc.nextInt();
		int ans = 0;
		for(int i = 1; i < N-1; i++) {
			if(p[i] < p[i-1] && p[i] > p[i+1])
				ans++;
			else if(p[i] > p[i-1] && p[i] < p[i+1])
				ans++;
		}
		System.out.println(ans);

	}

}

Measured memory_bytes: 23764
#include <iostream>

using namespace std;

int main(){
  int M, N;
  cin >> N >> M;
  string S[M];
  for(int i = 0; i < M; i++){
    cin >> S[i];
  }
  int ct = 0, ans = 1e9, ans_i = 0;
  for(int i = 0; i < M; i++){
    for(int j = 0; j < N; j++){
      if(S[i][j] == 'W') ct++;
    }
  }
  for(int j = 0; j < N + 1; j++){
    if(ct < ans){
      ans = ct;
      ans_i = j;
    }
    if(j == N) break;
    for(int i = 0; i < M; i++){
      if(S[i][j] == 'E') ct++;
      else ct--;
    }
  }
  cout << ans_i << ' ' << ans_i + 1 << endl;

  return 0;
}



Measured memory_bytes: 4588
import math

def main():
    a, b, x = map(int, input().split())

    a, b, x = 1.0, b / a, x / (a * a * b)
    x *= b

    if x * 2.0 > b:
        print(math.atan((b - x) / 0.5) * (180.0 / math.pi))
    else:
        print(90.0 - math.atan(x * 2 / (b * b)) * (180.0 / math.pi))

if __name__ == '__main__':
    main()


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

int main(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    set<int> s;
    for(auto&& i : a)
    {
        s.insert(i);
    }
    cout << s.size() << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main()
{
  int n,sum=0,av,ans=100000007;
  cin>>n;
  int a[n];
  rep(i,n)
  {
    cin>>a[i];
    sum+=a[i];
  }

  //書き換える数を全探索
  for(int i=-100;i<=100;i++)
  {
    int tmp=0;
    rep(j,n)  tmp+=pow(i-a[j],2);
    ans=min(ans,tmp);
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var edges = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var ab = edges[0];
        var bc = edges[1];
        Console.WriteLine(ab * bc / 2);
    }
}


Measured memory_bytes: 13268
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int n, m, x;
int c[12];
int a[12][12];
int unds[12];
int ans = INT_MAX, sum_cost = 0;

void dfs(int idx) {
  if (idx == n) return;

  sum_cost += c[idx];

  bool ok = true;
  for (int j = 0; j < m; j++) {
    unds[j] += a[idx][j];
    if (unds[j] < x) ok = false;
  }
  if (ok) ans = min(ans, sum_cost);

  dfs(idx + 1);
  sum_cost -= c[idx];
  for (int j = 0; j < m; j++) unds[j] -= a[idx][j];

  dfs(idx + 1);
}

int main() {
  cin >> n >> m >> x;
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  dfs(0);
  if (ans == INT_MAX)
    cout << -1 << endl;
  else
    cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3212
while(True):
	m,f,r=list(map(int,input().split()))
	if m==-1 and f==-1 and r==-1:
		break
	if m==-1 or f==-1:
		print("F")
	elif m+f>=80:
		print("A")
	elif m+f>=65:
		print("B")
	elif m+f>=50:
		print("C")
	elif m+f>=30:
		if r>=50:
			print("C")
		else:
			print("D")
	else:
		print("F")

Measured memory_bytes: 7612
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a;i<(a+n);i++)
using ll = long long;

ll pow(ll x, ll n, int mod) {
  ll ans = 1;
  while(n != 0){
      if(n&1) ans = ans*x % mod;
      x = x*x % mod;
      n = n >> 1;
  }
  return ans;
}

ll nCr(int n, int r, int mod) {
  ll res = 1;
  for(int i = 1; i <= r; i++) {
    res = res * (n-i+1) % mod * pow(i, mod-2, mod) % mod;
  }
  return res;
}

int main() {
  int mod = 1000000007;
  int n,a,b;
  cin >> n >> a >> b;
  ll temp = pow(2, n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod);
  // ※  temp 
  if (temp < mod) {
    temp %= mod;
    temp += mod; 
  } else if (mod < temp) {
    temp %= mod;
  }
  // temp %= mod;
  // temp += mod;
  temp %= mod;
  cout << temp << endl;
}


Measured memory_bytes: 256
use std::io;
fn main() {
    let mut l1 = String::new();
    let stdin = io::stdin();
    stdin.read_line(&mut l1).unwrap();
    let trimed = l1.trim_right();
    let n = trimed.parse::<usize>().unwrap();

    let mut v: std::vec::Vec<i32> = vec![
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4,
        1, 51,
    ];

    println!("{}", v[n - 1]);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define ll long long int
#define nl "\n"
#define input for(ll i=0;i<n;i++)  cin>>a[i];
#define M 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string str;
    cin>>str;
    int a=0,b=0;
    for(int i=0;str[i]!='\0';i++)
    {
        if(str[i]=='A')
            a++;
        else
            b++;
            
    }
    if(a==0||b==0)
        cout<<"No"<<nl;
    else
        cout<<"Yes"<<nl;
}


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

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    vector<int> num(n),ans(n);
    int max_num=0;
    for (int i = 0; i < n; i++){
        cin >> num.at(i);
        max_num = max(max_num, num.at(i));
        ans.at(i) = num.at(i);
    }
    sort(ans.begin(), ans.end(),greater<int>());
    int second_num = ans.at(1);

    for (int i = 0; i < n; i++){
        if(num.at(i)<max_num)
            cout << max_num << endl;
        else
            cout << second_num << endl;
    }
        return 0;
}

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

int main() {
  
  int a=0;
  
  int N;
  int M;
  int L;
  
  cin>>N>>M;
  
  
  vector<int> vec(M);
for (int i = 0; i < M; i++) {
  vec.at(i)=0;
}
  
  //vector<int> vec(M);
for (int i = 0; i < N; i++) {
  cin>>L;
  vector<int> vec1(L);
for (int i = 0; i < L; i++) {
  cin >> vec1.at(i);
}
  
  for (int i = 0; i < L; i++) {
  vec.at(vec1.at(i)-1)++;
}
  
}
  
  for (int i = 0; i < M; i++) {
  if(vec.at(i)==N){
    a++;
  }
}
  cout<<a<<endl;
  
  
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
#for i in range(m):
 # a[i] = int(input())
a = set([int(input()) for i in range(m)])
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

for j in range(2,n+1):
  dp[j] = (dp[j-1]+dp[j-2])%1000000007
  if j in a:
    dp[j] = 0
print(dp[n])

Measured memory_bytes: 86428
#include <iostream>
using namespace std;
int main(void){
	int N,T,A,minA,maxD=0,cnt=0;
	cin>>N>>T>>minA;
	while(--N){
		cin>>A;
		if(A<minA)minA=A;
		else if(A-minA==maxD)cnt++;
		else if(A-minA>maxD){
			cnt=1;
			maxD=A-minA;
		}
	}
	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define endl '\n'
#define N 1000001
#define mod 1e9+7
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,w;
	cin>>n>>w;
	ll wt[n],val[n];
	for(ll i=0;i<n;i++){
	    cin>>wt[i]>>val[i];
	}
	ll t[n+1][w+1];
	for(ll i=0;i<n+1;i++){
	    for(ll j=0;j<w+1;j++){
	        if(i==0 || j==0){
	            t[i][j]=0;
	        }
	    }
	}
	for(ll i=1;i<n+1;i++){
	    for(ll j=1;j<w+1;j++){
	        if(wt[i-1]<=j){
	            t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j]);
	        }else{
	            t[i][j]=t[i-1][j];
	        }
	    }
	}
	cout<<t[n][w];
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

int cost[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6};

// K桁をN本使ってできたときの先頭の数字の最大
int dp[10101][10101] = {0};
int back[10101][10101] = {0};
bool ok[9] = {0};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a;
    cin >> a;
    ok[a - 1] = true;
  }
  int k = n;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= n; j++)
      dp[i][j] = back[i][j] = -1;
  }
  dp[0][0] = 0;
  for (int i = 0; i < k; i++)
    for (int j = 0; j < n; j++)
      for (int l = 0; l < 9; l++) {
        if (!ok[l] || dp[i][j] < 0)
          continue;
        if (j + cost[l] <= n && dp[i + 1][j + cost[l]] < l) {
          dp[i + 1][j + cost[l]] = l;
          back[i + 1][j + cost[l]] = j;
        }
      }
  int now = n;
  while (dp[now][n] < 0)
    now--;
  int from = n;
  while (now > 0) {
    cout << dp[now][from] + 1;
    from = back[now][from];
    now--;
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 792832
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=2000010,O=1000000007;
int fac[N],invfac[N];
inline int fpow(int x,int n){
	int a=1;
	for(;n;n>>=1,x=(lint)x*x%O){
		if(n&1){
			a=(lint)a*x%O;
		}
	}
	return a;
}
inline int inv(int x){
	return fpow(x,O-2);
}
inline void gmath(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=(lint)fac[i-1]*i%O;
	}
	invfac[n]=inv(fac[n]);
	for(int i=n;i>=1;i--){
		invfac[i-1]=(lint)invfac[i]*i%O;
	}
}
inline int F(int x,int y){
	return (lint)fac[x+y]*invfac[x]%O*invfac[y]%O;
}
int x3,y3,x4,y4;
inline int solve(int sx,int sy,int tx,int ty){
	lint ans=0;
	for(int i=x3;i<=x4;i++){//enter from bottom && out from top
		ans-=(lint)F(i-sx,y3-1-sy)*F(tx-i,ty-y3)%O*(i+y3)%O;
		ans+=(lint)F(i-sx,y4-sy)*F(tx-i,ty-y4-1)%O*(i+y4+1)%O;
	}
	for(int j=y3;j<=y4;j++){//enter from left && out from top
		ans-=(lint)F(x3-1-sx,j-sy)*F(tx-x3,ty-j)%O*(x3+j)%O;
		ans+=(lint)F(x4-sx,j-sy)*F(tx-x4-1,ty-j)%O*(x4+j+1)%O;
	}
	return (ans%O+O)%O;
}
int main(){
	int sx[2],sy[2],tx[2],ty[2];
	sx[0]=ni-1,sx[1]=ni,x3=ni,x4=ni,tx[1]=ni,tx[0]=ni+1;
	sy[0]=ni-1,sy[1]=ni,y3=ni,y4=ni,ty[1]=ni,ty[0]=ni+1;
	gmath(tx[0]+ty[0]);
	lint ans=0;
	for(int a=0;a<2;a++){
		for(int b=0;b<2;b++){
			for(int c=0;c<2;c++){
				for(int d=0;d<2;d++){
					int sig=(a^b^c^d)?-1:1;
					ans+=sig*solve(sx[a],sy[b],tx[c],ty[d]);
				}
			}
		}
	}
	printf("%lld\n",(ans%O+O)%O);
	return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <cstring>

using namespace std;

int m,n,mp[10][10];
int cx,cy;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

int dfs(int x,int y,int count){
    int ret=0;
    if(count==0){
        if(x==cx||y==cy) return 1;
        return 0;
    }
    for(int i=0;i<4;++i){
        int tx=x,ty=y;
        while(1){
            tx +=dx[i];
            ty +=dy[i];
            if(tx<0||ty<0||tx>=m||ty>=n) break;
            if(mp[ty][tx]==1){
                mp[ty][tx]=0;
                ret +=dfs(tx,ty,count-1);
                mp[ty][tx]=1;
                break;
            }
        }
    }
    return ret;
}

int main(){
    while(cin>>m>>n,n){
        int num_house =0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                cin>>mp[i][j];
                if(mp[i][j]==2){
                    cx=j;cy=i;
                }
                if(mp[i][j]==1) ++num_house;
            }   
        }
        cout<<dfs(cx,cy,num_house)<<endl;
    }
    return 0;
}

Measured memory_bytes: 3084
#150c
import math

def isPrime(n):
	tmp=math.ceil(math.sqrt(n))
	if n==1:
		return False
	for i in range(2,tmp):
		if n%i==0:
			return False
	return True


x=int(input())
for i in range(x,100004):
	if isPrime(i):
		print(i)
		exit()

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

int GCD(int x, int y) {
  if (x < y) return GCD(y, x);
  int r = x % y;
  if (r == 0) return y;
  else return GCD(y, r);
}

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

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

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

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

  vector<int> ls(n);
  vector<int> rs(n);
  ls[0] = xs[0];
  for (int i = 1; i < n; i++) {
    ls[i] = GCD(ls[i - 1], xs[i]);
  }
  rs[n - 1] = xs[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    rs[i] = GCD(rs[i + 1], xs[i]);
  }

  int ans = 0;
  UpdateMax(ans, ls[n - 2]);
  UpdateMax(ans, rs[1]);
  for (int i = 0; i < n - 2; i++) {
    UpdateMax(ans, GCD(ls[i], rs[i + 2]));
  }
  cout << ans << endl;
}

Measured memory_bytes: 1408
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int N;
    cin >> N;
    vector<int> C(N-1,0),S(N-1,0),F(N-1,0);
    for (int i = 0; i < N-1; i++){
        cin >> C[i] >> S[i] >> F[i];
    } 

    for (int i = 0; i < N; i++){
        int t = 0;
        for (int k = i; k < N-1; k++){
            if (t < S[k]){
                t = S[k];
            } else if (t % F[k] == 0){
            } else {
                t += F[k] - t % F[k];
            }
            t += C[k];
        }
        cout << t << endl;
    }

            
            

    return 0;
}


Measured memory_bytes: 256
n = int(input())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
C = [abs(X[i] - Y[i]) for i in range(n)]
D = []
def distance(X, Y):  
  for k in range(1, 4):
    d = 0
    for j in range(len(X)):
      d += C[j] ** k
    d = d ** (1 / k)
    D.append(d)
  D.append(max(C))
  return D

distance(X, Y)
for i in range(4):
  print('{:.08f}'.format(D[i]))


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, K, C;
    string s;
    cin >> n >> K >> C >> s;

    vector<int> dpR(n + 1, 0);
    for (int i = n - 1; i > 0; --i) {
        if (s[i] == 'x') dpR[i - 1] = dpR[i];
        else dpR[i - 1] = max(dpR[i], dpR[min(i + C, n)] + 1);
    }

    vector<int> dpL(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'x') dpL[i + 1] = dpL[i];
        else dpL[i + 1] = max(dpL[i], dpL[max(i - C, 0)] + 1);
    }

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'x') continue;
        //cerr << i << " " << dpL[i] << " " << dpR[i] << "\n";
        if (dpL[i] + dpR[i] >= K) continue;
        //cerr << i << " " << dpL[max(i - C, 0)] << " " << dpR[min(i + C, n)] << "\n";
        if (dpL[max(i - C, 0)] + dpR[min(i + C, n)] + 1 >= K) {
            cout << i + 1 << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 3348
#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>
using namespace std;

typedef unsigned long long ll;

int main(void){
	int N;
	string M;

	while(cin>>N>>M, N){
		ll m = strtoll(&M[0],NULL,N);
		int n = N;
		vector<int> v,s;

		for(int i=2;i<=n;i++){
			if(n % i != 0) continue;

			v.push_back(i);
			s.push_back(0);
			while(n % i == 0){
				s[v.size()-1]++;
				n /= i;
			}
		}

		ll ans = ULLONG_MAX;
		for(int i=0;i<v.size();i++){
			ll tmp = m;
			ll zero = 0;
			while(tmp /= v[i]) zero += tmp;
			ans = min(ans,zero/s[i]);
		}

		cout<<ans<<endl;
	}

	return 0;
}

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

typedef struct List {
	struct List *next;
	int v;
} list;

int main()
{
	int i, j, N, M, K[100001], *L[100001];
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++) {
		scanf("%d", &(K[i]));
		L[i] = (int*)malloc(sizeof(int) * (K[i] + 1));
		for (j = 1; j <= K[i]; j++) scanf("%d", &(L[i][j]));
	}

	int m = 0;
	list **adj = (list**)malloc(sizeof(list*) * (N + M + 2)), *d = (list*)malloc(sizeof(list) * 200000);
	for (i = 1; i <= N + M; i++) adj[i] = NULL;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= K[i]; j++) {
			d[m*2].v = N + L[i][j];
			d[m*2+1].v = i;
			d[m*2].next = adj[i];
			d[m*2+1].next = adj[N+L[i][j]];
			adj[i] = &(d[m*2]);
			adj[N+L[i][j]] = &(d[m*2+1]);
			m++;
		}
	}
	
	int head, tail, q[200001], flag[200001] = {};
	list *p;
	q[0] = 1;
	flag[1] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		for (p = adj[q[head]]; p != NULL; p = p->next) {
			if (flag[p->v] == 0) {
				flag[p->v] = 1;
				q[tail++] = p->v;
			}
		}
	}
	
	for (i = 1; i <= N; i++) if (flag[i] == 0) break;
	if (i > N) printf("YES\n");
	else printf("NO\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	string S;
	cin >> N >> S;
	for(int i = 2*N-2; i >= 0; i -= 2) S[i] = (S[i] == 'B') ? 'W' : 'B';
	int cnt_b = 0, cnt_w = 0;
	long long ans = 1, mod = 1000000007;
	for(int i = 0; i < 2*N; i++) {
		if(S[i] == 'W') cnt_w++;
		else {
			cnt_b++;
			ans = ans * max(0, cnt_w) % mod;
			cnt_w--;
		}
	}
	if(cnt_b != N) ans = 0;
	for(int i = 1; i <= N; i++) ans = ans * i % mod;
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 720
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define mp make_pair
#define enld endl

int main() {
	lint a;
	cin >> a;
	cout << a + a * a + a * a * a << enld;
}

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1000000007;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	rep(i,n){
		if(i % 2 == 0){
			if(!(s[i] == 'R' || s[i] == 'U' || s[i] == 'D')){
				cout << "No\n";
				return 0;
			}
		}
		else{
			if(!(s[i] == 'L' || s[i] == 'U' || s[i] == 'D')){
				cout << "No\n";
				return 0;
			}
		}
	}
	cout << "Yes\n";
	return 0;
}



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

int main() {
	int A,B,K,c=0,d;
	cin >>A>>B>>K;
	for(int d=A;d>=1;d--){
		if(A%d==0 && B%d==0){
			c++;
			if(c==K)cout <<d;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sumvec(vector<S>&a){return accumulate(all(a),S());}
template<class S>S maxvec(vector<S>&a){return *max_element(all(a));}
template<class S>S minvec(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

vvl comb(ll n, ll r) {
  vvl v(n + 1,vl(n + 1, 0));
  for (ll i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (ll j = 1; j < v.size(); j++) {
    for (ll k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}


int main(void){
  	cin.tie(0);
  	ios::sync_with_stdio(false);
  	
  	ll n;
  	cin>>n;
  	vl h(n);
  	cin>>h;
  	vl cost(n,INF);
  	cost[0]=0;
  	
  	range(i,1,n){
  	    ll a,b=INF;
  	    a=abs(h[i]-h[i-1]) + cost[i-1];
  	    if(i>1) b=abs(h[i]-h[i-2]) + cost[i-2];
  	    //cout<<a<<" "<<b<<" ";
  	    cost[i]=min(a,b);
  	    //puta(cost[i]);
  	}
  	
  	puta(cost[n-1]);

}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;

int main() {
	int n, m;
	cin >> n >> m;
	if (n == m)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    LL n;
    cin>>n;
    LL x=1000*(n/1000)+bool(n%1000)*1000;
    cout<<x-n;

}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{

    string s;
    cin >> s;

    int c0 = 0;
    rep(i, s.size()) { if (s[i] == '0') c0++; }

    put(2 * min(c0, (int)s.size() - c0));
    

    return 0;
}

Measured memory_bytes: 3752
N = int(input())
A = [int(i) for i in input().split()]

count = 0
for i in range(N) :
    if i==0 :
        continue
    if A[i]<A[i-1] :
        count += abs(A[i]-A[i-1])
        A[i] += abs(A[i]-A[i-1])

print(count)

Measured memory_bytes: 32208
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>

using namespace std;
int main() {

    string S;
    cin>>S;

    if(S[0]==S[1] || S[1]==S[2] || S[2]==S[3]){

        cout<<"Bad"<<endl;
    }
    else{

        cout<<"Good"<<endl;
    }

}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;

typedef int64_t ll;
typedef uint64_t ull;

const ll LINF = 9187201950435737471;
const ll nLINF = -9187201950435737472;
const int INF = 2139062143;
const int LOL = 450;
const int nINF = -2139062144;
const ull ULINF = numeric_limits<ull>::max();
const int MAXN = 3e5 + 15;
const ll MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = acos(-1);
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

#define all(_v) _v.begin(), _v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)(v.size())
#define sqr(_v) ((_v) * (_v))
#define eb emplace_back
#define pb push_back
#define mod(x, m) ((x) % m + ((x) < 0 ? m: 0))
#define vi vector<int>
#define pi pair<int,int>


inline void IO() {
#if(DEBUG_LEVEL > 0)
    freopen("../input.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
}

template <typename T>
istream& operator >> (istream& in, vector<T>& a) {
    for (auto& i : a)
        in >> i;
    return in;
}

template <typename T>
ostream& operator << (ostream& out, const vector<T>& a) {
    for (auto& i : a) {
        out << i << " ";
    }
    return out;
}

template <typename T, typename D>
istream& operator >> (istream& in, pair<T, D>& a) {
    in >> a.first >> a.second;
    return in;
}

template <typename T, typename D>
ostream& operator << (ostream& out, const pair<T, D>& a) {
    out << a.first << " " << a.second;
    return out;
}

#define int ll

inline void solve() {
    int n, k, ans = 0;
    cin >> n >> k;
    vi a(n);
    cin >> a;
    int inside = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[i]) {
                inside++;
            }
        }
    }
    ans = (inside * k) % MOD;
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            if (a[j] < a[i]) {
                cnt++;
            }
        }
        int now = (cnt * ((((k - 1) * k) / 2) % MOD)) % MOD;
        ans = (ans + now) % MOD;
    }
    cout << ans;
}

signed main() {
    IO();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  double x[n], y[n];
  rep(i, n) cin >> x[i] >> y[i];
  
  vector<int> v(n);
  iota(v.begin(), v.end(), 0);
  double ans = 0.0;
  while (1) {
    rep(i, n-1) {
      ans += sqrt(pow(x[v[i+1]]-x[v[i]], 2) + pow(y[v[i+1]]-y[v[i]], 2));
    }
    if (!next_permutation(v.begin(), v.end())) break;
  }
  for (int i = 1; i <= n; ++i) ans /= i;
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

Measured memory_bytes: 256
a = gets.chomp.to_i
b = gets.chomp.to_i
c = gets.chomp.to_i
x = gets.chomp.to_i

cnt = 0
(0..a).each do |i|
  (0..b).each do |j|
    (0..c).each do |k|
      cnt += 1 if i * 500 + j * 100 + k * 50 == x
    end
  end
end

puts cnt

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

typedef long long ll;

int max(int a, int b){
  if(a > b) return a;
  else return b;
}
int min(int a, int b){
  if(a < b) return a;
  else return b;
}

  ll n;

void func(ll cur, int use, ll *counter){

  if(cur > n) return;
  if(use == 0b111) ++(*counter);

  func(cur*10 + 3, use | 0b001, counter);
  func(cur*10 + 5, use | 0b010, counter);
  func(cur*10 + 7, use | 0b100, counter);

}

int main(){

  scanf("%d",&n);
  ll res = 0;
  func(0, 0, &res);
  printf("%d",res);
  return 0;

}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
  int D, E;
  while(cin >> D >> E, D || E) {
    double ans = 1e9;
    for(int x = 0; x <= D; x++) {
      int y = D - x;
      ans = min(ans, fabs(sqrt(x*x + y*y) - E));
    }
    printf("%.10f\n", ans);
  }
  
  return 0;
}

Measured memory_bytes: 1196
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	read  = bufio.NewReader(os.Stdin)
	write = bufio.NewWriter(os.Stdout)
)

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func yesno(result bool) {
	if result {
		fmt.Fprintln(write, "Yes")
	} else {
		fmt.Fprintln(write, "No")
	}
}

func printansStr(result bool, a, b string) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func printansInt(result bool, a, b int) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func main() {
	defer write.Flush()

	var a, b, c int
	fmt.Fscan(read, &a, &b, &c)
	fmt.Fprintln(write, max(c-(a-b), 0))
}


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

const int INF = 11000000;
bool num[INF+1] = {false};	//素数ならfalse

int prime4[1000];

void devide( int n )
{
	int i,j;
	for( i = 2; i*i <= n;i++ ){
		for( j = i*2; j <= n; j += i ){
			num[j] = true;
		}
	}
}
int GetPrime4( int n )
{
	int i,cnt = 0;
	for( i = 2; i <= n-8; i++ ){
		if( num[i] == false && num[i+2] == false && num[i+6] == false && num[i+8] == false ){
			prime4[cnt] = i+8;
			cnt++;
		}
	}
	return cnt;
}

int main(){
	int cnt;
	devide( INF );
	cnt = GetPrime4( INF );
	int n,i;

	while( cin >> n ){
		if( n == 0 )
			break;
		for( i = 0;prime4[i] <= n;i++ );
		cout << prime4[i-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 11904
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int a,b,c;
    cin>>a>>b>>c;
    if(b-a==c-b)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
	return 0;
}

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

int main() {
	int N;
	int L[100000], R[100000];
	int result = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> L[i] >> R[i];

		result += R[i] - L[i] + 1;
	}
	cout << result << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int[] w = new int[n];
        int s1 = 0;
        int s2 = 0;
        for(int i = 0; i < n; i++){
            w[i] = Integer.parseInt(sc.next());
            s2 += w[i];
        }
        
        int min = 10000;
        int abs;
        for(int i = 0; i < n-1; i++){
            s1 += w[i];
            s2 -= w[i];
            abs = Math.abs(s1 - s2);
            if(abs < min){
                min = abs;
            }
        }
        
        System.out.println(min);
    }
}

Measured memory_bytes: 21844
#include<stdio.h>
#include"algorithm"
using namespace std;
int main()
{
	int n,k,x,min=1000000000,i,h[100000];
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++)
	scanf("%d",&h[i]);
	sort(h,h+n);
	for(i=0;i+k<=n;i++)
	if(h[i+k-1]-h[i]<min)
	min=h[i+k-1]-h[i];
	printf("%d",min);
}

Measured memory_bytes: 512
fun main (args:Array<String>){
    val list = readLine()!!.split(" ").map(String::toInt)
    if (list[0] == list[1] && list[0] != list[2]) {
        print("Yes")
        return;
    }
    if (list[0] == list[2] && list[0] != list[1]) {
        print("Yes")
        return;
    }
    if (list[1] == list[2] && list[0] != list[1]) {
        print("Yes")
        return;
    }
    print("No")
}


Measured memory_bytes: 36356
"use strict";
main(require("fs").readFileSync("/dev/stdin", "utf8").replace(/\r?\n$/, "").split(/\r?\n/));

function main(lines){
	var x = lines[1].split(" ").map(Number);
	var y = lines[2].split(" ").map(Number);

	function distance(x, y, p){
		var sum = x.map(function(x,i){return Math.pow(Math.abs(x-y[i]),p)}).reduce(function(a,b){return a+b});
		return Math.pow(sum, 1/p)
	}
	console.log(distance(x, y, 1));
	console.log(distance(x, y, 2));
	console.log(distance(x, y, 3));
	console.log(Math.max.apply(0, x.map(function(x,i){return Math.abs(x-y[i])})));
}

Measured memory_bytes: 16080
#include <stdio.h>
int main(void) {
	int n, a[3000], ans,i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	ans = 0;
	for (i = 1; i <= n; i++) {
		ans = ans + a[i];
	}
	ans = ans - n;
	printf("%d", ans);






	return 0;
}


Measured memory_bytes: 128