akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main()
{
	int h[1000];
	int w[1000];
	int num=0;
	int i,j,k;
	
	//input
	while(1){
		scanf("%d %d",&h[num],&w[num]);
	//	printf("%d %d\n",h[num],w[num]);
		if(h[num]==0&&w[num]==0) break;
		num++;		
	}
	
	
	//output
	for(i=0;i<num;i++){
		
		for(k=0;k<w[i];k++) 
			printf("#");
		printf("\n");
		
		for(j=1;j<h[i]-1;j++){
			printf("#");
			for(k=1;k<w[i]-1;k++) printf(".");
			printf("#");
			printf("\n");
		}
		
		for(k=0;k<w[i];k++) 
			printf("#");
		printf("\n");
		
		
		printf("\n");
	}
	
	return 0;
}


Measured memory_bytes: 2100
# -*- coding: utf-8 -*-

n, m = map(int, input().split())

lamps = [list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))

ans = 0

for i in range(1 << n):
    for r in range(m):
        on_sum=0
        for j in range(n):
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1

        if on_sum % 2 != p[r]:
            break

    else:
        ans += 1

print(ans)


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

const int nm = 2e5;
int n, a[nm], x = 0, s[nm], t;
long long k;

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}

	fill(s, s + n, -1);
	for (int i = 0;; i++, k--, x = a[x]) {
		if (!k) {
			cout << x + 1 << endl;
			return 0;
		}
		if (s[x] < 0)
			s[x] = i;
		else {
			t = i - s[x];
			break;
		}
	}
	k %= t;
	for (int i = 0; i < k; i++)
		x = a[x];

	cout << x + 1 << endl;
}


Measured memory_bytes: 5196
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n; cin >> n;
	vector<string> grid(n);
	for(int i = 0; i < n; i++) cin >> grid[i];
	int ans = -1;
	for(int i = 0; i < n; i++){
		vector<int> dist(n, -1);
		queue<int> q; q.push(i); dist[i] = 0;
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(int j = 0; j < n; j++){
				if(grid[u][j] == '1' && dist[j] == -1){
					dist[j] = dist[u] + 1;
					q.push(j);
				}
			}
		}
		bool bad = false;
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				if(grid[j][k] == '1' && abs(dist[j] - dist[k]) != 1){
					bad = true;	
				}	
			}
		}
		if(!bad){
			ans = max(ans, 1 + *max_element(dist.begin(), dist.end()));
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
    int l,r,d;
    int cnt = 0;

    scanf("%d %d %d", &l, &r, &d);

    for (int i = 1;; i++){
        if((d * i) > r)
        {
            printf("%d", cnt);
            return 0;
        }
        if((d * i) >= l){
            cnt++;
        }
    }
    return 0;
}


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

int main() {
	// your code goes here
	long long int a,b,c,d;
	
	cin>>a>>b>>c>>d;
	
	long long int x1,x2,y1,y2;
	
	x1=max(a,b);
	x2=min(a,b);
	
	y1=max(c,d);
	y2=min(c,d);
	

	long long int ans = max(x2*y1, max(x1*y2,max(x1*y1, x2*y2)));
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define parity __builtin_parity

typedef long long ll;
const int N = 20, N2 = 65554, mod = 1000000007;

int n, K, ALL;
int k[N], f[N][N2];
int fact[N2], finv[N2];

inline void add(int &x, const int y) {x += y - mod, x += x >> 31 & mod;}
inline void fma(int &x, const int y, const int z) {x = (x + (ll)y * z) % mod;}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init(int n) {
	int i;
	for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	finv[n] = PowerMod(fact[n], mod - 2);
	for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
}

inline ll A(int n, int r) {return n < r ? 0 : (ll)fact[n] * finv[n - r] % mod;}

int main() {
	int i, j, c, r, ans = 0;
	scanf("%d%d", &n, &K), ALL = ~(-1 << n), init(ALL + 1);
	for (i = 0; i < K; ++i) scanf("%d", k + i), --k[i];
	std::reverse(k, k + K), **f = 1;
	for (i = 0; i < K; ++i)
		for (j = 0; j <= ALL; ++j) if (r = f[i][j]) {
			add(f[i + 1][j], r);
			for (c = 0; c < n; ++c) if (!(j >> c & 1))
				fma(f[i + 1][j | 1 << c], r, (A(ALL - j - k[i], ~(-1 << c)) << c) % mod);
		}
	for (i = 0; i <= ALL; ++i)
		ans = (ans + ll(parity(i) ? -f[K][i] : f[K][i]) * fact[ALL & ~i]) % mod;
	ans = ((ll)ans << n) % mod;
	printf("%d\n", ans + (ans >> 31 & mod));
	return 0;
}

Measured memory_bytes: 4352
N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
rest = 0
for i, a in enumerate(A):
    if rest == 0:
        ans += a // 2
        rest = a % 2
    else:
        if (a + rest) % 2 == 0:
            ans += (a + rest) // 2
            rest = 0
        else:
            ans += (rest + a) // 2
            rest = 1 if a != 0 else 0

print(ans)


Measured memory_bytes: 7072
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define int ll
//#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair 
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
#define PI 3.141592653589
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using pld = pair <ld, ld>;

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

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

template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}

template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}

inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
}

signed main()
{
    Start();
    int n, m, c;
    cin >> n >> m >> c;
    vector <int> b(m);
    cin >> b;
    vector <vector <int>> a(n, vector <int> (m));
    cin >> a;
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = 0;
        for (int j = 0; j < m; ++j)
        {
            cur += a[i][j] * b[j];
        }
        ans += bool(cur + c > 0);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
class Main {
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder(480);
		for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++)
				sb.append(i).append("x").append(j).append("=").append(i*j).append("\n");
		System.out.print(sb);
	}
}

Measured memory_bytes: 8848
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    ll a, b;
    cin >> a >> b;

    ll ans = abs(a - b);
    if (ans % 2 == 0) {
        ll aa = a - ans / 2;
        ll bb = a + ans / 2;
        if (abs(b - aa) == ans / 2) {
            print(aa);
        } else {
            print(bb);
        }
    } else {
        print("IMPOSSIBLE");
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(){
  int n,k,x,y,count=0;
  std::cin >> n >> k >> x >> y;
  
  for(int i=1; i<=n; i++){
    if(i <= k){
      count += x;
    }
    else{
      count += y;
    }
  }
  
  std::cout << count << std::endl;
  
  return 0;
}


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

int main() {
    int n;
    scanf("%d", &n);
    int maxH = 0, res = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x >= maxH) {
            res++;
        }
        maxH = max(maxH, x);
    }
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 256
print([0, 0, 0, 61, 230, 865, 3247, 12185, 45719, 171531, 643550, 2414454, 9058467, 33985227, 127504505, 478366600, 794717734, 733354121, 261943303, 776803305, 580025381, 51688048, 44657419, 737209731, 604119499, 159693437, 858533109, 639056669, 549054109, 996291083, 531294469, 23314687, 783022045, 855462856, 649970414, 68697295, 409213624, 604356692, 88638656, 978442997, 534833116, 763737161, 785892908, 123883652, 639213333, 181836645, 998121103, 124885216, 501575626, 39816123, 113468411, 799008836, 775465589, 256852905, 664630886, 971550783, 751629411, 51018086, 702530485, 725438992, 696683714, 792638194, 221791721, 149602322, 414054379, 986519078, 981760191, 305799096, 515140586, 406959393, 975058685, 245601370, 324759692, 673385295, 191483611, 570246669, 427196161, 781042769, 569725155, 842176273, 25328739, 847501730, 206282374, 353770801, 323137024, 371653459, 940737264, 123820509, 915711339, 847205021, 252858375, 718889563, 866398347, 738390145, 133009077, 333099663, 170591295, 329869205, 616680192, 597534442, 388130742][int(input())])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
//typedef pair<long long,long long> P;
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int func(vector<int> h){
  int res=0;
  int num=h.size();
  int m=INT_MAX;
  REP(i,num){
    m = min(m,h[i]);
  }
  REP(i,num){
    h[i] -= m;
  }
  res += m;
  vector<int> temp;
  REP(i,num){
    if(h[i]==0){
      if(!temp.empty()){
        res += func(temp);
        temp.clear();
      }
    }else{
      temp.push_back(h[i]);
      if(i==num-1){
        if(!temp.empty()){
          res += func(temp);
          temp.clear();
        }
      }
    }
  }
  return res;
}
      
  
int main(){ 
  int n;
  cin>>n;
  vector<int> h(n);
  REP(i,n){
    cin>>h[i];
  }
  int ans;
  ans = func(h);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<complex>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ll  long long
#define pb push_back
#define sz(v)               ((int)((v).size()))
#define all(x)          (x).begin(),(x).end()
#define REP(i, v)       for(int i=0;i<sz(v);i++)
using namespace std;
typedef pair<int,int> pii;
ll k;
ll arr[51];
int main()
{
	scanf("%lld",&k);
	if(k == 0)
	{
		printf("4\n3 3 3 3\n");
		return 0;
	}
	if(k == 1)
	{
		printf("3\n1 0 3\n");
		return 0;
	}
	ll n = min(50LL,k);
	for(int i = 0 ; i < n ; ++i) arr[i] = i;
	for(int i = 0 ; i < n ; ++i) arr[i] += 1LL*(k / n);
	ll rem = k % n;
	int ind = 0;
	printf("%d\n",n);
	while(rem--)
	{
		arr[ind] += n;
		for(int i = 0 ; i < n ;++i) if(i != ind) arr[i]--;
		ind++;
	}
	for(int i = 0 ; i < n ; ++i)
		printf("%lld ",arr[i]);

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue> 
using namespace std;
int main() 
{int n,d,x,ans=0;
 cin>>n>>d>>x;
 int a[n+1];
 for (int i=1;i<=n;i++){
 cin>>a[i];
 a[i]=(d+a[i]-1)/a[i];
 ans+=a[i];}
 cout<<ans+x;                                        
 system("pause");
 return 0;
}        


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i,n) {
    cin >> a[i];
    b[i]=a[i];
  }
  sort(b.begin(),b.end());
  int c1 = b[n/2-1];
  int c2 = b[n/2];
  rep(i,n) {
    if(a[i]>=c2) cout << c1 << endl;
    else cout << c2 << endl;
  }
}


Measured memory_bytes: 3712
s = input()
n = len(s)
res = 0
sum = 0
c = {}
c[0] = 1
p = 1
for i in range(n - 1, -1, -1):
    sum = (sum + int(s[i]) * p) % 2019
    if sum in c:
        res += c[sum]
    p = (p * 10) % 2019
    c[sum] = c.get(sum, 0) + 1

print(res)

Measured memory_bytes: 9256
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll m = 1e9 + 7;
const int lim = 5000;
vector <vector<ll>> ncr(5001, vector<ll>(5001));
ll cc(ll s, ll r){
    s-=3*r;
    if(s < 0) return 0;
    if(s == 0) return 1;
    return ncr[s+r-1][r-1];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i <= lim; i++){
        ncr[i][0] = 1;
        //ncr[i][1] = 1;
        //if(i > 0) ncr[i][i-1] = i;
    }
    for(int i = 1; i <= lim; i++) for(int j = 1; j <= i; j++){
        ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
        ncr[i][j]%=m;
    }
    //cout << ncr[2000][199] << "\n";
    ll s; cin >> s;
    ll ans = 0;
    for(ll i = 1; i <= s; i++){
        ans+=cc(s, i);
        ans%=m;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 199228
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
typedef long long unsigned int ll;
typedef pair<int, int> P;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

#define rep(i,n) for(auto i=0; i<(n); i++)
#define isValidPoint(x, y, mx, my) x >= 0 && x  < mx && y >= 0 && y < my

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

const int MOD = 1000000007;

struct Pony
{
    long a, b;
 
    Pony(long a_, long b_)
    {
        a = a_;
        b = b_;
    }
 
    bool operator<(const Pony &another) const
    {
        return b < another.b;
    };
};

int fac(int k){
    int sum = 0;
    for (int i = 1; i <= k; ++i)
    {
        sum += i;
    }
    return sum;
}

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

  int  n, d;
  cin >> n >> d;

  vector<vector<int>> x(n);

  rep(i, n) {
    rep(j, d) {
      int a;
      cin >> a;
      x[i].push_back(a);
    }
  }

  int cnt = 0;
  rep(i, n-1) {
    for(int j = i+1; j < n; j++) {
      int dis2 = 0;
      rep(k, d) {
        dis2 += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
      }
      if ((int)(sqrt(dis2)) * (int)(sqrt(dis2)) == dis2) cnt++;
    }
  }

  cout << cnt << endl;

}


Measured memory_bytes: 888
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 302
#define ckmax(x,y) x = x > y ? x : y

using namespace std;

int n, m;
int a[N][N], b[N][N], f[N][N][N], g[N][N][N], h[2][N][N][N];
char s[N][N];

int find(int ,int ,int ,int);
int get(int ,int ,int ,int);

int main(){
	scanf("%d%d", &n, &m);
	memset(f, -1, sizeof f);
	for(int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	for(int i = 1; i <= n; ++i)
		for(int j = m; j; --j)
			a[i][j] = (s[i][j] == s[i][j + 1] ? a[i][j + 1] : 0) + 1;
	for(int j = 1; j <= m; ++j)
		for(int i = n; i; --i)
			b[i][j] = (s[i][j] == s[i + 1][j] ? b[i + 1][j] : 0) + 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j){
			f[i][j][j] = b[i][j];
			for(int k = j + 1; k <= m; ++k)
				f[i][j][k] = min(f[i][j][k - 1], s[i][k] == s[i][k - 1] ? b[i][k] : 0);
		}
	for(int j = 1; j <= m; ++j)
		for(int i = 1; i <= n; ++i){
			g[j][i][i] = a[i][j];
			for(int k = i + 1; k <= n; ++k)
				g[j][i][k] = min(g[j][i][k - 1], s[k][j] == s[k - 1][j] ? a[k][j] : 0);
		}
	int ans = 0;
	while(f[1][1][m] < n){
		++ans;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				for(int k = j; k <= m; ++k){
					f[i][j][k] += f[i + f[i][j][k]][j][k];
					if(f[i][j][k]) ckmax(h[0][j][i][i + f[i][j][k] - 1], k - j + 1);
				}
		for(int j = 1; j <= m; ++j)
			for(int i = 1; i <= n; ++i)
				for(int k = i; k <= n; ++k){
					g[j][i][k] += g[j + g[j][i][k]][i][k];
					if(g[j][i][k]) ckmax(h[1][i][j][j + g[j][i][k] - 1], k - i + 1);
				}
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				for(int k = m; k >= j; --k)
					ckmax(f[i][j][k], max(f[i][j][k + 1], h[1][i][j][k]));
		for(int j = 1; j <= m; ++j)
			for(int i = 1; i <= n; ++i)
				for(int k = n; k >= i; --k)
					ckmax(g[j][i][k], max(g[j][i][k + 1], h[0][j][i][k]));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 311552
#include <stdio.h>

int main()
{
    long i,j,k,n,m,l;
    long A[101][101],B[101][101],C[101][101]={0};
    scanf("%d %d %d",&n,&m,&l);
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d ",&A[i][j]);
        }
    }
    for(i=0;i<m;i++){
        for(j=0;j<l;j++){
            scanf("%d ",&B[i][j]);
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<l;j++){
            for(k=0;k<m;k++){
                C[i][j] += A[i][k]*B[k][j];
            }
        printf("%ld",C[i][j]);
        if(j<l-1)
            printf(" ");
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<"="<<x
#define nl cout<<"\n"
#define frn(i,n) for(int i = 0;i < n;i++)
#define fr(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define trav(x,c) for(auto &x:c)
using namespace std;

int toint(string s) {
  int ans = 0;
  for(char x: s) ans = ans*10 + (x - '0');
  return ans;
}

int sum(int x) {
  int s = 0;
  while(x) {
    s += x%10;
    x /= 10;
  }
  return s;
} 

bool equal(string s) {
  for(int i = 0,j = s.size()/2;j < s.size();i++,j++) {
    if(s[i] != s[j]) return false;
  }
  return true;
}

int main() {
  int n,m;
  cin>>n>>m;
  int a[n],b[n],c[m],d[m];
  frn(i,n) cin>>a[i]>>b[i];
  frn(i,m) cin>>c[i]>>d[i];
  int ans[n+1];
  frn(i,n) {
    ll dist = LLONG_MAX;
    for(int j = m-1;j >= 0;j--) {
      int d1 = abs(a[i]-c[j]) + abs(b[i]-d[j]);
      if(d1 <= dist) {
        dist = d1;
        ans[i+1] = j+1;
      }
    }
  }
  fr(i,1,n+1) {cout<<ans[i];nl;}
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

int n, a[SIZE];

bool check(int x) {
  int s[SIZE];

  s[0] = 0;
  for(int i=0;i<n;i++){
    s[i+1] = a[i] >= x ? 1 : -1;
    s[i+1] += s[i];
  }

  int num[SIZE] = {};
  int base = 1e5;

  int sum = 0;
  for(int i=1;i<=n;i++){
    num[base+s[i]]++;
    sum += s[i] >= 0;
  }

  ll res = 0;

  for(int i=0;i<n;i++){
    res += sum;

    if (s[i+1] < s[i]) {
      sum += num[base+s[i+1]];
    } else {
      sum -= num[base+s[i]];
    }

    num[base+s[i+1]]--;
    sum--;
  }

  debug(x);
  debug(res);

  return res * 2 >= (ll)n * (n-1) / 2 + n;
}

int main(){

  scanf("%d", &n);

  for(int i=0;i<n;i++){
    scanf("%d", a+i);
  }

  int l = 1, r = 1e9;

  while(l<r){
    int mid = (l+r+1) / 2;

    if (check(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }

  cout << l << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <numeric>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
const int MOD = 1e9+7;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

const int MX = 2000100 + 5;
int fac[MX+5],inv[MX+5];
 
int power(int x,int y,int p){
	int res=1;
	x=x%p;
	while(y){
		if(y&1)res=(res*x)%p;
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
void init(){
  int n=MX+4;
	fac[0] = 1;
  for(int i=0;i<n;++i)fac[i+1]=fac[i]*(i+1)%MOD;
  inv[n]=power(fac[n],MOD-2,MOD);
  for(int i=n-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%MOD;
}
int comb(int n,int r){return (fac[n]*inv[r])%MOD*inv[n-r]%MOD;}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);
    init();

    int K; cin >> K;
    string S; cin >> S;
    int T=K+SZ(S);
    int ans=0;
    rng(i,SZ(S),K+SZ(S)+1) {
        ans+=(comb(T,i)*power(25,T-i,MOD))%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 35496
#include<bits/stdc++.h>
using namespace std;
#define watch(x) cout<<(#x)<<" is "<<(x)<<endl;
#define mod 1000000007
#define pb push_back
#define endl '\n'



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

	int n;
	cin>>n;
	string s;
	cin>>s;
	int count =0;
	for(int i=0;i<=n-3;i++)
	{
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C') count++;
	}
	cout<<count<<endl;

}

Measured memory_bytes: 256
import sys
from functools import lru_cache

sys.setrecursionlimit(2*10**5)

# 入力
N, Ma, Mb = map(int, input().split())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


# タイプAがxグラム, タイプBがyグラムの物質の最小生成コストを動的計画法により求める
@lru_cache(maxsize=None)
def f(i, x, y):
    return (
        10**18 if (i < 0 and not (x == y == 0)) or x < 0 or y < 0 else
        0 if x == 0 and y == 0 else
        min(
            f(i - 1, x - a[i - 1], y - b[i - 1]) + c[i - 1],
            f(i - 1, x, y)
        )
    )


# タイプAとタイプBの物質の比率がMa:Mbとなるような物質の最小コストを求める
A = sum(a)
B = sum(b)
opt = min(
    f(N, x, Mb * (x // Ma))
    for x in range(Ma, A + 1)
    if x % Ma == 0 and Mb * (x // Ma) <= B
)
ans = (
    opt if opt < 10**18 else
    -1
)

# 出力
print(ans)


Measured memory_bytes: 135420
n, a, b = list(map(int, input().split(' ')))
ss = 0
for i in range(1, n + 1):
    x = i
    s = 0
    br = False
    while x > 0:
        s += x % 10
        x = int(x / 10)
        if s > b:
            br = True
            break
    if not br and s >= a:
        ss += i
print(ss)

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

// 各桁の和を計算する関数
int findSumOfDigits(int n){
    int sum = 0;
    while(n > 0){
        // nが0になるまで
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(){
    int N,A,B;
    cin >> N >> A >> B;
    int total = 0;
    for(int i = 1; i <= N; ++i){
        int sum = findSumOfDigits(i); // iの各桁の和
        if(sum >= A && sum <= B){
            total += i;
        }
    }

    cout << total << endl;
}


Measured memory_bytes: 256
a[1000];main(){
	int n,m,c,d;
	for(scanf("%d%d",&n,&m);m--;)for(scanf("%d%d",&c,&d);c<d;c++)a[c]=1;
	for(c=d=0;c<n;c++)d+=a[c]*2;
	*a=!printf("%d\n",d+n+1);
}

Measured memory_bytes: 600
#include <iostream>
#include <cstdio>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define MOD1 1000000007;
#define MOD2 1000007
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
/* ここからが本編 */
/*  */
 
ull pow(ull x,ull n) {
  ull res = 1;
  while(n > 0) {
    if(n&1) res = res * x;
    x = x * x;
    n >>= 1;
  }
  return res;
}
int dic_op(char str[14])
{
  int j;
  long long f = 1;
  long long g = 0;
  for(j = 0;;j++) {
    if(str[j] == 'A')
      g += f * 1;
    else if(str[j] == 'C')
      g += f * 2;
    else if(str[j] == 'G')
      g += f * 3;
    else if(str[j] == 'T')
      g += f * 4;
    else break;
    f *= 5;
  }
  return g; 
}
 
int main()
{
  int i,j,k,l;
  int n;
  long ans = 0;
  static char dic[100000000];
  char opstr[7];
  char str[13];
  cin >> n;
  for (i = 0; i < n; i++) {
    scanf("%s %s",opstr,str);
    if(opstr[0] == 'i') {
      dic[dic_op(str)] = 1;
    }
    else if(opstr[0] == 'f') {
      if(dic[dic_op(str)] == 1)
        puts("yes");
      else
        puts("no");
      j++;
    }
  }
  return 0;
}

Measured memory_bytes: 10644
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	ll c[n];
	bool aced[n];
	fill(c, c + n, 0);
	fill(aced, aced + n, false);
	for (int i = 0; i < m; i++){
		int x;
		string s;
		cin >> x >> s;
		x--;
		if (s == "AC"){
			aced[x] = true;
		}else{
			if (!aced[x]){
				c[x]++;
			}
		}
	}
	ll ans = 0, sum = 0;
	for (int i = 0; i < n; i++){
		if (aced[i]){
			ans++;
			sum += c[i];
		}
	}
	printf("%lld %lld\n", ans, sum);
}

Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int inf = 1000000000;

bool binary(int t, vector<int> a){

  int l = 0;
  int r = a.size()-1;
  while( l != r ){
    int m = (l+r)/2;
    if( t < a[ m ] ) r = m;
    else if( t > a[ m ] ) l = m + 1;
    else break;
  }
  return t == a[ (l+r)/2 ];
}

int main(void) {

  int n;
  cin >> n;
  vector<int> s(n);
  for(int i=0; i<n; i++) cin >> s[i];
  int q;
  cin >> q;
  vector<int> t(q);
  for(int i=0; i<q; i++) cin >> t[i];

  int cnt = 0;
  for(int i=0; i<q; i++){
    cnt += binary(t[i], s);
  }
  cout << cnt << endl;

  return 0;
}

// EOF

Measured memory_bytes: 3856
import java.util.*;

public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int w = sc.nextInt();
        String t = "";
        for (int i = 0 ; i < s.length() ; i++) {
            if (i % w == 0) t += s.charAt(i);
        }
        System.out.println(t);
    }
}

Measured memory_bytes: 25940
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <map>
#include <queue>
#include <numeric>
#include <climits>
#include <functional>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
using ll = unsigned long long;
const ll mod = 1000000007;
string al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//bool less_sec(const pair<int, int>&a, const pair<int, int>&b) {
//	return a.second > b.second;
//}
int n, a, b, c;
vector<string> v;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
    cin >> a >> b;
    if(a > b) cout << a-1 << endl;
    else cout << a << endl;
    

    return 0;
}

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

typedef long long ll;

ll mod = 1e9 + 7;
ll num[100005];

ll q_pow(ll a,ll b)
{
	ll res = 1;
	while( b )
	{
		if( b & 1 )
		{
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,k;
	cin >> n >> k;
	ll ans = 0;
	for (int i = k; i >= 1; i--)
	{
		int t = k / i;
		num[i] = q_pow(t,n);
		for (int j = 2; j * i <= k; j++)
		{
			num[i] = ( num[i] - num[i*j] + mod ) % mod;
		}
		ans += ( num[i] * i ) % mod;
		ans %= mod;
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 4384
primes = [2]

def is_prime(num):
    root = num ** 0.5
    for prime in primes:
        if root < prime:
            break
        if num % prime == 0:
            return 0
    return 1

def create_primes(primes, max):
    for i in range(primes[-1] + 1,max):
        if is_prime(i):
            primes += [i]

count = 0
n = int(input())
s = [int(input()) for _ in range(n)]

create_primes(primes, int(max(s) ** 0.5))

print(sum(is_prime(i) for i in s))

Measured memory_bytes: 7256
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INF 999999999
using namespace std;


int main(){
          int w,h,n;
          cin >> w >> h >> n;
          int x[n],y[n],a[n];
          REP(i,n)  cin >> x[i] >> y[i] >> a[i];

          int lx=0,ly=0,hx=w,hy=h;

          REP(i,n){
                    if(a[i]==1 and x[i]>lx)       lx=x[i];
                    else if(a[i]==2 and x[i]<hx)  hx=x[i];
                    else if(a[i]==3 and y[i]>ly)  ly=y[i];
                    else if(a[i]==4 and y[i]<hy)  hy=y[i];
          }
          cout << max(0,hx-lx)*max(0,hy-ly) << endl;
          return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <random>
#include <cassert>
#include <algorithm>    
#include <iostream>
#include <chrono>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <bitset>
#define pb push_back
#define mk make_pair
#define eb emplace_back
#define eps 1e-8
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
// #define int long long


using namespace std;
typedef long double ld;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef tuple<int, int, int> tiii;
typedef vector<int> vii;
typedef vector<long double> vd;
const int inf = 1e9;
const long long INF = 1e18;
const int M = 1e9 + 7;





signed main()
{
	int n, k, q;
	cin >> n >> k >> q;
	std::vector<int> a(n + 1, 0);
	for(int i = 0; i < q; ++i) {
		int x;
		cin >> x;
		a[x]++;
	}
	for(int i = 1; i <= n; ++i) {
		if(a[i] + k > q) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
    
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void resolve() {
    int n;
    cin >> n;
    VI t(n), x(n), y(n);
    REP(i,0,n) cin >> t[i] >> x[i] >> y[i];
    {
        int xdiff = abs(x[0]);
        int ydiff = abs(y[0]);
        int tdiff = t[0];
        if (xdiff + ydiff > tdiff) {
            cout << "No" << endl;
            return;                
        }
        if ((xdiff + ydiff) % 2 != tdiff % 2) {
            cout << "No" << endl;
            return;
        }        
    }
    REP(i,1,n) {
        if (x[i] == x[i-1] && y[i] == y[i-1]) {
            if ((t[i] - t[i-1]) % 2 == 0) {
                cout << "No" << endl;
                return;
            }
        } else {
            int xdiff = abs(x[i] - x[i-1]);
            int ydiff = abs(y[i] - y[i-1]);
            int tdiff = t[i] - t[i-1];
            if (xdiff + ydiff > tdiff) {
                cout << "No" << endl;
                return;                
            }
            if ((xdiff + ydiff) % 2 != tdiff % 2) {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

int main() {
    resolve();
    
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
   int a, b, c;
   cin>>a>>b>>c;

   bool y=false;
   if(a==b && a!=c) y=true;
   if(a==c && a!=b) y=true;
   if(b==c && b!=a) y=true;

   if(y) cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
   return 0;
}


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

int cmp(const void *a, const void*b){
  return *(int*)a - *(int*)b;
}

int main(){
  while(1){
    int n;
    scanf("%d", &n);
    if(n==0) break;
    int a[n], i;
    for(i=0;i<n;i++) scanf("%d", &a[i]);

    qsort(a, n, sizeof(int), cmp); 
    int min = a[n-1], temp;
    for(i=0;i<n-1;i++){
      temp = a[i+1] - a[i];
      if(temp<min) min = temp;
    }
    printf("%d\n", min);
  }
  return 0;
}



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




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

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

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

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

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

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<int, int>;

/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}

const int INF = 1001001001;

int main() {
	int n, m, x;
	cin >> n >> m >> x;
	vector<int> c(n);
	vector<vector<int>> a(12, vector<int> (12));
	rep(i, n) {
		cin >> c[i];
		rep(j, m)cin >> a[i][j];
	}
	int ans = INF;
	rep(i, 1<<n) {
		int cost = 0;
		vector<int> b(m);
		rep(j, n) {
			if (i >> j & 1) {
				cost += c[j];
				rep(k, m) b[k] += a[j][k];
			}
		}
			bool ok = true;
			rep(k, m) if (b[k] < x)ok = false;
			if (ok==true)ans = min(ans, cost);
	}
	if (ans == INF)cout << -1;
	else cout << ans;
	return 0;
}













Measured memory_bytes: 3604
#include <cstdio>
int n,k,a[110][9],cnt[110][11];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=13;i++){
		for(int j=1;j<=7;j++)a[i][j]=7*i+j-7;
	}
	for(int i=1;i<=11;i++){
		for(int j=0;j<11;j++)cnt[i][j]=cnt[i-1][j];
		for(int j=1;j<=5;j++)cnt[i][(a[i][j]+a[i][j+1]+a[i][j+2]
		+a[i+1][j]+a[i+1][j+1]+a[i+1][j+2]
		+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2])%11]++;
	}
	n-=2;
	printf("%d\n",n<0?0:cnt[11][k]*(n/11)+cnt[n%11][k]);
	return 0;
} 

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

int main() {
  string a,b;
  cin>>a>>b;
  for(int i=0;i<a.size();i++){
    if(i==a.size()-1 && a.size()>b.size()) {
      cout<<a[i]<<endl;
      break;
    }
    cout<<a[i]<<b[i];
    if(i==a.size()-1) cout<<endl;
  }
  return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll N;
  scanf("%lld", &N);

  vector<ll> list;
  for (ll i = 0; i < N; i++) {
    ll v;
    scanf("%lld", &v);
    list.emplace_back(v);
  }
  sort(list.rbegin(), list.rend());

  ll ans = list[0];
  ll i = 1;
  ll count = 1;
  for (;;) {
    ll val = list[i];

    if (count == N - 1) {
      break;
    }
    ans += val;
    // cout << "val:" << val << endl;
    count++;

    if (count == N - 1) {
      break;
    }
    ans += val;
    // cout << "val:" << val << endl;
    count++;

    i++;
  }
  cout << ans << endl;
}


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

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

  return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
const int INF = 0x3f3f3f3f;
ll a[100005];
map<ll, ll> cnt;
int main() {
  int n, q;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  ll sum = 0;
  for (auto x : cnt) {
    sum += x.ff * x.ss;
  }
  cin >> q;
  while (q--) {
    ll b, c;
    cin >> b >> c;
    sum -= cnt[b] * b, sum += cnt[b] * c;
    cout << sum << endl;
    cnt[c] += cnt[b], cnt[b] = 0;
  }
}

Measured memory_bytes: 10284
S = input()
len_S = len(S)
n = len_S // 2
A = "01" * n
B = "10" * n
if len_S % 2 == 1:
    A += "0"
    B += "1"
an, bn = 0, 0
for s, a, b in zip(S, A, B):
    if s == a:
        bn += 1
    else:
        an += 1
print(min(an, bn))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;

unsigned int randxor() {
  static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned int t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}




int main() {
  int D;
  cin >> D;
  vector<int> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<int>> s(D, vector<int>(26));
  vector<int> last_day(26, 0);
  vector<int> t(D);
  rep(i,D) rep(j,26) cin >> s[i][j];

  int score = 0;
  int res = 0;
  auto Scoring = [&](int d, int id, int oid) {
    if (oid != -1) score -= s[d - 1][oid];
    score += s[d - 1][id];
    last_day[id] = d;
    for (int i = 0; i < 26; i++) score -= c[i] * (d - last_day[i]); 
    res = max((int)1e6 + score, 0);
  };

  auto init = [&](){
    while (res < 10000) {
      for (int i = 0; i < D; i++) {
        int q = randxor() % 26;
        t[i] = q;
        Scoring(i + 1, q, -1);
      }
    }
  };

  //計算  
  init();
  rep(p, 40000000) {

    int d = randxor() % D;
    int change_q = randxor() % 26;    
    int old_q = t[d];
    t[d] = change_q;
    int old_res = res;
    int old_score = score;
    Scoring(d + 1, change_q, old_q);
    if (res < old_res) {
      t[d] = old_q;
      res = old_res;
      score = old_score;
    }
  }

  //cout << res << endl;
  rep(i,D) cout << t[i] + 1 << endl;
  return 0;
} 

Measured memory_bytes: 3684
n = int(input())
v_ary = list(map(int, input().split()))
c_ary = list(map(int, input().split()))

a_minus_b = 0

for i in range(n):
    if v_ary[i] - c_ary[i] > 0:
        a_minus_b += v_ary[i] - c_ary[i]
print(a_minus_b)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
    string s; cin >> s;
    map<char,int> mp;
    for(int i = 0; i < 4; i++){
        mp[s[i]]++;
    }
    for(auto& x:mp){
        if(x.second != 2){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
unsigned long long a[100005];
unsigned long long b[100005];
map<string,unsigned long long> mp;
int cmp(char aa,char bb){
	return aa<bb;
}
int main(){
	int n;
	cin>>n;
	string s;
	long long ans=0;
	for(int i=0;i<n;i++){
		cin>>s;
		char tmp[15];
		for(int j=0;j<s.length();j++){
			tmp[j]=s[j];
		}
		sort(tmp,tmp+s.length());
		for(int j=0;j<s.length();j++){
			s[j]=tmp[j];
		}
		ans+=mp[s];
		mp[s]++;
	}
	cout<<ans;
	return 0;
} 

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

int main(void)
{
    long long x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    
    vector<long long> a_v, b_v, c_v;
    
    long long tmp;
    for (int i = 0; i < a; i++) { cin >> tmp; a_v.push_back(tmp); } 
    for (int i = 0; i < b; i++) { cin >> tmp; b_v.push_back(tmp); } 
    for (int i = 0; i < c; i++) { cin >> tmp; c_v.push_back(tmp); } 
    sort(a_v.begin(), a_v.end(), greater<long long>());
    sort(b_v.begin(), b_v.end(), greater<long long>());
    sort(c_v.begin(), c_v.end(), greater<long long>());
    a_v.resize(x);
    b_v.resize(y);
    c_v.resize(min(c, x+y));
    
    vector<long long> all = a_v;
    all.insert(all.end(), b_v.begin(), b_v.end());
    all.insert(all.end(), c_v.begin(), c_v.end());
    sort(all.begin(), all.end(), greater<long long>());
    all.resize(x+y);
    cout << accumulate(all.begin(), all.end(), 0LL) << endl;

    return 0;
}


Measured memory_bytes: 6836
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,K;
  
  cin >> A >> B >> C >> K;
  
  int sum=A+B;
  int max;
  
  if(sum>=K){
    if(A>=K){
      max=K;
    }else if(A<K){
      max=A;
    }
  }else if(sum<K){
    max=A-(K-sum);
  }
  
  cout << max << endl;
  
  return 0;
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
using namespace std;
int main()
{
   char a,b;
   cin>>a>>b;
   if(a=='H'&&b=='H')
        cout<<'H';
   else if(a=='D'&&b=='D')
        cout<<'H';
else
    cout<<"D"<<endl;

 return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<k;i++)
	ans+=a[i];
	cout<<ans;
			    
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
  int m,n;
  while(cin>>m>>n,m){
    bool s[7654321]={};
    int i=m,j=0,k;
    for(;j<=n;i++)
      if(!s[i])for(k=2,j++;i*k<7654321;k++)s[i*k]=1;
    cout<<i-1<<endl;
  }
  return 0;
}

Measured memory_bytes: 10548