akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a>b?a:b)
int compare(const void *a,  const void *b)
{
    return *(int*)a - *(int*)b;
}
int main(void)
{
    int x,count=0;
    scanf("%d",&x);
    switch(x){
        case 3:;
        case 5:;
        case 7: printf("YES"); return 0;
    }
    printf("NO");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define int long long int
#define double long double
#define inf (int)(1e15)
#define all(x) (x).begin(), (x).end()
#define pair pair<int, int>
typedef vector<int> vi;   // Vector of long long
typedef vector<vi> vvi;   // Vector of vi
typedef vector<pair> vii; // Vector of pairs
typedef vector<vii> vvii; // Vector of Vector of pairs
typedef vector<bool> vb;  // Vector of bool
#define pq priority_queue // Max heap (To convert to min heap, use negative sign before every value)
#define ff first          // For pairs
#define ss second
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, -1, 0, 1};
const int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}, dy8[] = {1, -1, 1, 0, -1, 1, -0, -1};
#define testcases(t) \
    int(t);          \
    cin >> (t);      \
    while ((t)--)
signed main()
{

    int l, r, d;
    cin >> l >> r >> d;
    int ans = (r - l + 1) / d;
    if (l % d == 0 && d != 1)
        ans++;
    cout << ans << endl;
    return 0;
}


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

int64_t mgcd(int64_t a, int64_t b){
    if(b > a) return mgcd(b, a);
    if(b == 0) return a;
    if(a % b  == 0) return b;
    return mgcd(b, a % b);
}

template<class Elem>
class segTree{
    function<Elem(Elem,Elem)> f;
    Elem e;
    ll lgN;
    ll tree_size;
    ll pos_first;

    Elem *tree;
    pair<ll,ll> *idx2range;  // tree[i]の管理する区間を [ l, r ) で持つ

    inline ll getParent(ll n){
        return (n-1)/2;
    }
    inline pair<ll,ll> getChildren(ll n){
        return make_pair(n*2+1,n*2+2);
    }

public:
    segTree(ll N, function<Elem(Elem,Elem)> func, Elem default_value){
        f=func;
        e=default_value;
        lgN=1;
        while((1<<lgN)<N) lgN++;
        tree_size=(1LL<<(lgN+1))-1;
        pos_first=(1LL<<lgN)-1;

        tree=new Elem[tree_size];
        idx2range=new pair<ll,ll>[tree_size];

        for(ll i=0;i<tree_size;i++) tree[i]=e;

        idx2range[0]=make_pair(0LL,1LL<<lgN);
        for(ll i=1;i<tree_size;i++){
            const ll pl=idx2range[getParent(i)].first;
            const ll pr=idx2range[getParent(i)].second;
            const ll pm=(pl+pr)/2;

            idx2range[i]=(i%2==1)?make_pair(pl,pm):make_pair(pm,pr);
        }
    }
    ~segTree(){
        delete[] tree;
        delete[] idx2range;
    }

    void setValue(ll pos, Elem x){
        ll index=pos_first+pos;

        tree[index]=x;
        while(index>0){
            index=getParent(index);
            tree[index]=f(tree[getChildren(index).first],tree[getChildren(index).second]);
        }
    }

    // [ left, right ) に f をやった結果を返す
    Elem query(ll left, ll right, ll node=0){
        if(left<=idx2range[node].first && idx2range[node].second<=right) return tree[node];
        if(right<=idx2range[node].first || idx2range[node].second<=left) return e;
        
        return f(query(left,right,getChildren(node).first),query(left,right,getChildren(node).second));
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    int64_t n;
    static int64_t a[100000];
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];

    segTree<int64_t> st(n, mgcd, 0);
    for(int i=0;i<n;i++) st.setValue(i, a[i]);

    int64_t ans = 0;
    for(int i=0;i<n;i++){
        ans = max(ans, mgcd(st.query(0, i), st.query(i+1, n)));
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
    int x, a, b;
  cin >> x >> a >> b;
  if (a >= b) {
   cout << "delicious" << endl;
  }
  else if (a < b && (b - a) <= x) {
    cout << "safe" << endl;
  }
  else {
    cout << "dangerous" << endl;
  }
}


Measured memory_bytes: 256
input()
try:
    while True:
        a, b, c = map(int, input().split())
        if (a**2 == b**2 + c**2) or (b**2 == a**2 + c**2) or (c**2 == b**2 + a**2) :
            print("YES")
        else:
            print("NO")
except EOFError:
    pass


Measured memory_bytes: 5604
from functools import reduce
import functools
import fractions
 
@functools.lru_cache(maxsize=None)
def gcd(*numbers):
  return reduce(gcd_, numbers)

@functools.lru_cache(maxsize=None)
def gcd_(a, b):
  if (b == 0):
    return a
  return gcd(b, a % b)
 
sum = 0
K = int(input())
 
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if (i == j) & (j == k):
        sum += gcd(i,j,k)
      elif (i == j) & (j != k):
        sum += gcd(i,j,k)*3
      elif (i != j) & (j == k):
        sum += gcd(i,j,k)*3
      elif (i != j) & (j != k):
        sum += gcd(i,j,k)*6

print(sum)


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

int main(){
    int N;
    cin >> N;
    vector<double> A(N);

    for (int i = 0;i < N;i++){
        cin >> A.at(i);
    }

    double sum = 0.0;
    for (int i = 0;i < N;i++){
        sum += 1.0 / A.at(i);
    }
     sum = 1.0 / sum;

    cout << setprecision(16) << sum << endl;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
a=[int(i) for i in input().split()]

a.sort()
dp=[0]*(K+1)

for i in range(0,a[0]):
    dp[i]='Second'

for i in range(a[0],K+1):
    for j in a:
        if i<j:
            dp[i]='Second'
            break
        if dp[i-j]=='Second':
            dp[i]='First'
            break
        if j==a[-1]:
            dp[i]='Second'

print(dp[-1])


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

using namespace std;

int main() {
    int H, W;
    cin >> H >> W;

    int dp[H][W][4];

    char input;
    for(int r = 0; r < H; r++)
    {
        for (int c = 0; c < W; c++)
        {
            cin >> input;
            if (input == '#')
            {
                for (int i = 0; i < 4; i++)
                {
                    dp[r][c][i] = 0; 
                }
            } else {
                for (int i = 0; i < 4; i++)
                {
                    dp[r][c][i] = 1; 
                }
            }
        }
    }

    for(int side = 0; side < 4; side++)
    {
        if(side == 0)
        {
            for(int r = 1; r < H; r++)
            {
                for(int c = 0; c < W; c++)
                {
                    if (dp[r][c][0] != 0)
                    {
                        dp[r][c][0] += dp[r - 1][c][0];
                    }
                }
            }
        } else if (side == 1)
        {
            for(int r = 0; r < H; r++)
            {
                for(int c = W - 2; c >= 0; c--)
                {
                    if (dp[r][c][1] != 0)
                    {
                        dp[r][c][1] += dp[r][c + 1][1];
                    }
                }
            }
        } else if (side == 2) {
            for(int r = H - 2; r >= 0; r--)
            {
                for(int c = 0; c < W; c++)
                {
                    if (dp[r][c][2] != 0)
                    {
                        dp[r][c][2] += dp[r + 1][c][2];
                    }
                }
            }
        } else if (side == 3) {
            for (int r = 0; r < H; r++)
            {
                for (int c = 1; c < W; c++)
                {
                    if (dp[r][c][3] != 0)
                    {
                        dp[r][c][3] += dp[r][c - 1][3];
                    }
                }
            }
        }
    }

    int max = 0;
    for (int r = 0; r < H; r++)
    {
        for (int c = 0; c < W; c++)
        {
            if (dp[r][c][0] + dp[r][c][1] + dp[r][c][2] + dp[r][c][3] > max)
            {
                max = dp[r][c][0] + dp[r][c][1] + dp[r][c][2] + dp[r][c][3];
            }
        }
    }

    cout << max - 3;
}


Measured memory_bytes: 62720
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
using ulong = unsigned long;
using ll = long long;

struct Node{
	vector<Node*> nodes;
	int solve(int k){
		int ret = solveV(0, k, nullptr);
		for(Node* n : nodes){
			ret = min(ret, n -> solveV(1, k, this) + solveV(1, k, n));
		}
		return ret;
	}
	int solveV(int len2 , int k, Node* from){
		int cnt = 0;
		if(len2 > k){
			cnt++;
		}
		for(Node* n : nodes) if(n != from){
			cnt += n -> solveV(len2 + 2, k, this);
		}
		// cout<<cnt<<endl;
		return cnt;
	}
};

int main(){
	int n, k;
	cin >> n >> k;
	vector<Node> nodes(n);
	for(int i=0;i<n-1;i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		nodes[a].nodes.push_back(&nodes[b]);
		nodes[b].nodes.push_back(&nodes[a]);
	}
	int ans = 1e9;
	for(Node& n : nodes){
		ans = min(ans, n.solve(k));
		// cout<<ans<<endl;
	}
	cout << ans << endl;
	return 0;
}



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

int maximo(int a, int b){
    if(a>b) return a;
    return b;
}

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

    int n, ans = 0, dif;
    cin >> n;
    int v[n], c[n];

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

    for(int i = 0; i < n; i++){
        dif = v[i] - c[i];
        if(dif >= 0) ans+=dif;
    }

    cout << ans << endl;



    
    
    
    
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author hakamada
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC1181 solver = new ABC1181();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC1181 {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int A = in.nextInt();
            int B = in.nextInt();

            if (B % A == 0) {
                out.println(A + B);
            } else {
                out.println(B - A);
            }

        }

    }
}



Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int n;
	long long int sumer = 0;
	int temp;
	int ave;
	int data[60000];
	int result[60000] = {};
	int count;
	for (count = 0; true; count++) {
		cin >> n;
		sumer = 0;
		temp = 0;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> temp;
			data[i] = temp;
			sumer += temp;
		}
		ave = sumer / n;
		for (int i = 0; i < n; i++) {
			if (data[i] <= ave) {
				result[count]++;
			}
		}
		
	}
	for (int i = 0; i < count; i++) {
		cout << result[i] << endl;
	}
	return 0;
}
/*
//単一連結リストの実装
struct ListNode {
	int data;
	struct ListNode* next;
};*//*
int ListLength(struct ListNode* head) {
	struct ListNode* current = head;
	int count = 0;
	while (current != NULL) {
		count++;
		current = current -> next;
	}
	return count;
}


int main()
{
	int n = 0;
	int owari = 11451414;
	int result[50010] = {};
	int sa = owari;
	int count = 0;
	while (true) {
		int dataset[50010];
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> dataset[i];
		}
		sort(dataset, dataset + n);
		sa = owari;
		for (int i = 1; i < n; i++) {
			if (abs(dataset[i] - dataset[i - 1]) < sa) {
				sa = abs(dataset[i] - dataset[i - 1]);
			}
		}
		result[count] = sa;
		count++;
	}
	for (int i = 0; i < count; i++) {
		cout << result[i] << endl;
	}
	return 0;
}
*/


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

#define iota(i,n,b,s) for(int i=int(b);i!=int((b)+(s)*(n));i+=(s))
#define range(i,n,m) iota(i,(((n)>(m))?((n)-(m)+1):((m)-(n)+1)),(n),((n)>(m)?-1:1))
#define rep(i,n) iota(i,(n),0,1)

#define INF (1e9)
#define EPS (1e-9)
#define cons(a,b) (make_pair(a,b))
#define car(a) (a.first)
#define cdr(a) (a.second)
#define cadr(a) (car(cdr(a)))
#define cddr(a) (cdr(cdr(a)))
#define all(a) a.begin(), a.end()
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;

typedef long long Integer;
typedef double Real;

template<class S, class T>
ostream& operator<<(ostream& os, pair<S,T> p) {
  os << '(' << car(p) << ", " << cdr(p) << ')';
  return os;
}

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

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

int main() {

  for (Integer a, b; cin >> a >> b, cin; ) {
    Integer x = max(a,b);
    Integer y = min(a,b);
    while (y > 0) {
      x %= y;
      Integer t = x;
      x = y;
      y = t;
    }
    //cerr << cons(a,b) << ' ' << cons(x, y) << endl;
    cout << x << ' ' << (a / x * b) << endl;
  }

  return 0;
}

Measured memory_bytes: 1156
#include <cstdio>
int main(){
  int m, d;
  scanf("%d %d", &m, &d);
  
  int d1;
  int d10;
  
  int count = 0;
  for (int i = 1; i <= m; i++){
    for (int j = 1; j <= d; j++){
      d1 = (int) (j / 10);
      d10 = j % 10;
      if ((d1 >= 2) && (d10 >= 2) && (i == (d1* d10))){
        count++;
      }
    }
  }
  printf("%d\n", count++);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#define lint unsigned long long int
#define FOR(x, to) for(int x=0; x<(int)(to); x++)
#define DUMP(ar) for(auto itd=begin(ar); itd != end(ar); itd++) cout << "["s << itd - begin(ar) << "]:"s << *itd << endl
#define DUMPL(ar) for(auto itd=begin(ar); itd != end(ar); itd++) { cout << *itd; if(end(ar)-itd > 1) cout << ' '; } cout << endl;
#define COUT(x) cout << (x) << endl
#define ALL(ar) ar.begin(), ar.end()
#define LOOPD(i) cout << "ループ["s << i << "]回目---------------"s << endl
using namespace std;

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

    int k, x;
    cin >> k >> x;
    if(500 * k >= x){
        COUT("Yes");
    }else{
        COUT("No");
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
    int a,b,c,d = 0;
    cin >> a >> b >> c >> d;
    bool yn = 0;
    if(abs(a-c) <= d){
        yn = 1;
    }else if(abs(a-b)<= d && abs(b-c) <= d){
        yn = 1;
    }
    if(yn){
        cout << "Yes";
    }else{
        cout << "No";
    }
}

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

using namespace std;
int main(void){
    int H=0, W=0;
    cin >> H >> W;
    vector<string>L(H, " ");
    rep(i, H) cin >> L[i];
    for(int i=H-1; i>=0; i--){  //行削除は下から
        if(L[i].find('#')==-1){
            L.erase(L.begin()+i);
        }
    }
    vector<int>col(W,0);
    rep(i, L.size()) rep(j, W) if(L[i][j]=='.') col[j]+=1;
    for(int j=W-1; j>=0; j--){ //列削除は右から
        if(col[j]==L.size()){
            for(int i=0; i <L.size(); i++) L[i].erase(L[i].begin()+ j);
        }
    }
    rep(i, L.size()) cout << L[i] << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String[] arr = line.split(" ");
		int a = Integer.parseInt(arr[0]);
		int b = Integer.parseInt(arr[1]);
		int c = Integer.parseInt(arr[2]);
		List<Integer> l = Arrays.asList(a, b, c);
		Collections.sort(l);
		for (int i = 0; i < l.size(); i++) {
			if (i != 0) {
				System.out.print(" ");
			}
			System.out.print(l.get(i));
		}
		System.out.println();
	}
}

Measured memory_bytes: 16916
a, b, c, d = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
x = (b // c) - (a // c)
if a % c == 0:
  x += 1
y = (b // d) - (a // d)
if a % d == 0:
  y += 1

lcm = c * d // gcd(c, d)  
z = (b // lcm) - (a // lcm)
if a % lcm == 0:
  z += 1

print(b - a + 1 - (x + y - z))

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

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    long long res = 0;
    for (int i = 0; i < n - 1; i++) {
        res += res / (k - 1) + 1;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3104
# import math
# import fractions

n = int(input())
a = list(map(int, input().split()))

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)


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

int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    int cnt=0,f=-1,b=-1;
    for(int i=0;i<n;i++)
    {
        if((i+1)!=a[i])
        {
            cnt++;
            if(f==-1)   f=i;
            else    b=i;
        }
    }
    if(cnt==0)  printf("YES");
    else if(cnt>2)   printf("NO");
    else
    {
        if(((f+1)==a[b]) && ((b+1)==a[f]))  printf("YES");
        else    printf("NO");
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int n = Integer.parseInt(scanner.nextLine());

		char[] list = scanner.nextLine().toCharArray();
		String temp = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
		char[] alph = temp.toCharArray();
		StringBuilder sb = new StringBuilder();

		for(int i = 0; i < list.length; i++) {

			for(int j = 0; j < 27; j++) {

				if(list[i] == alph[j]) {

					list[i] = alph[j + n];
					break;
				}
			}
		}

		for(char t: list) {

			sb.append(String.valueOf(t));

		}

		System.out.println(sb.toString());


	}
}


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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long int> cnt(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        long long int s = 1;
        while (i * s <= n) {
            cnt[i * s]++;
            s++;
        }
    }
    unsigned long long int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (i * cnt[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 81392
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    string s;
    cin>>s;
    int max=0;
    int cnt=0;
    int f;
    rep(i,s.size()){
        cnt=0;
        f=i;
        while(s[f]=='A' || s[f]=='T' || s[f]=='C' || s[f]=='G'){
             f++;
             cnt++;
        }
        if(cnt>max) max=cnt;
    }
    cout<<max<<endl;
}

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

int main() {
  int N, sum, a, b, C;
  sum = 0;
  cin >> N;
  a = 10*10*10*10*10*10*10*10*10;
  b = N;
  
  for (int i = 0; i < 9; i++){
    a /= 10;
    sum += b / a;
    b %= a;
  }

  C = N % sum;
  
  if (C == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
# coding:utf-8

import sys


input = sys.stdin.readline
MOD = 100000


def inpl(): return list(map(int, input().split()))


while 1:
    N, M, S = inpl()
    if N == 0:
        break
    N *= N
    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        for j in range(S + 1):
            if i <= j:
                dp[i][j] += dp[i][j - i] + dp[i - 1][j - i]
            if j - 1 >= M:
                dp[i][j] -= dp[i - 1][j - 1 - M]
            dp[i][j] %= MOD

    # TLE!!!
    # for i in range(1, M + 1):
    #     for j in range(1, N + 1)[::-1]:  # j - 1の値が更新されるのを防ぐために降順
    #         for k in range(i, S + 1):  # 合計値は必ずi以上になる
    #             dp[j][k] += dp[j - 1][k - i]
    #             dp[j][k] %= MOD

    print(dp[N][S])



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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n,k; cin >> n >> k;
  vector<ll> v(n); cin >> v;
  for(int i = k; i < n; ++i){
    if(v[i] > v[i-k]) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int n, k;
  cin >> n >> k;
  ul ans = 0;
  for (int b=k+1; b<=n; ++b) {
    ans += n/b * (b-k);
    if (n%b!=0) {
      ans += max(0, n-(n/b*b)-max(0, k-1));
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
H, W, K = map(int, input().split())
C = [list(input()) for i in range(H)]

ans = 0

for h in range(2**H):
    for w in range(2**W):
        h_s = bin(h)[2:].zfill(6)[::-1]
        w_s = bin(w)[2:].zfill(6)[::-1]
        cnt = 0
        for i, c in enumerate(C):
            for j, a in enumerate(c):
                if h_s[i] == "0"\
                and w_s[j] == "0"\
                and a == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)


Measured memory_bytes: 9236
#include <iostream>
#include <cmath>
#include <iomanip>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>

#define int64 long long
using namespace std;

int main()
{
	int64 nn;
	cin >> nn;
	int64 ans = 1, tmp;
	bool flag = true;
	for(int64 ii = 0;ii < nn;ii++)
	{
		cin >> tmp;
		if(tmp == 0)
		{
			cout << "0" << endl;
			return 0;
		}
		else if(1000000000000000000 / tmp < ans)
		{
			flag = false;
		}
		else if(flag)
		{
			ans *= tmp;
		}
	}
	if(flag)
	{
		cout << ans << endl;
	}
	else
	{
		cout << "-1" << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import java.math.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    long a=0,b=0,c=0,d=0,e=0;
    for(int i=0;i<n;i++){
        String str = sc.next();
        switch(str.charAt(0)){
            case 'M': a++; break;
            case 'A': b++; break;
            case 'R': c++; break;
            case 'C': d++; break;
            case 'H': e++; break;
        }
    }
    System.out.println(
a*b*c + 
a*b*d + 
a*b*e + 
a*c*d + 
a*c*e + 
a*d*e + 
b*c*d + 
b*c*e + 
b*d*e + 
c*d*e);
  }
}


Measured memory_bytes: 47608
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<cstring>
#include<iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;


#define MAX_V 10000
#define INF 10000000000

struct edge{int to;long long cap,rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,long long cap)
{
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(int s)
{
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while(!que.empty())
	{
		int v = que.front();que.pop();
		for(int i = 0;i < G[v].size();++i)
		{
			edge &e = G[v][i];
			if(e.cap > 0 && level[e.to] < 0)
			{
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v ,int t,long long f)
{
	if(v == t)return f;
	for(int &i = iter[v];i < G[v].size() ;++i)
	{
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to])
		{
			long long d = dfs(e.to,t,min(f,e.cap));
			if(d > 0)
			{
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

long long Dinic(int s,int t)
{
	long long flow = 0;
	while(1)
	{
		bfs(s);
		if(level[t] < 0)return flow;
		memset(iter,0,sizeof(iter));
		long long f;while((f = dfs(s,t,INF)) > 0)flow += f;
	}
}
	

int main()
{
	int n;cin >> n;
	ll ans = 0;
	REP(i,n)
	{
		int a;cin >> a;
		if(a > 0){add_edge(0,i+1,a);ans += a;}
		else add_edge(i+1,n+1,-a);
		for(int j = (i+1);j <= n;j += i+1)
		{
			//add_edge(i+1,j,INF);
			add_edge(j,i+1,INF);
		}
	}
	
	cout << ans - Dinic(0,n+1) << endl;
	
	return 0;
}

Measured memory_bytes: 640
n = gets.chomp.to_i

a = []
n.times do
  inst, num = gets.chomp.split(" ")
  if inst == 'insert'
    a.unshift(num)
  elsif inst == 'delete'
    i = nil
    a.each do |aa|
      if aa == num
        i = a.index(aa)
        break
      else
        next
      end
    end
    if i
      a.delete_at(i)
    end
  elsif inst == 'deleteFirst'
    a.shift
  else
    a.pop
  end
end

puts a.join(" ")


Measured memory_bytes: 76096
#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() {
  double l;
  cin >> l;
  double ans = pow(l,3)/27;
  printf("%.10f\n", ans);
  return 0;
}


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

ll a[200005],cs[N];

int main()
{

    string s;

    cin >> s;

    if(s=="SAT") cout << 1;

    else if(s=="FRI") cout << 2;

    else if(s=="THU") cout << 3;

    else if(s=="WED") cout << 4;

    else if(s=="TUE") cout << 5;

    else if(s=="MON") cout << 6;

    else if(s=="SUN") cout << 7;

    return 0;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = [input() for i in range(N)]

L = []
for s in S:
    c = "".join(sorted(s))
    L.append(c)
L.sort()
S = set(L)
# print(L)
C = Counter(L)
# print(C)
cnt = 0
for s in S:
    cnt += C[s] * (C[s] - 1) // 2
print(cnt)


Measured memory_bytes: 31664
#include <iostream>

using namespace std;

int main(void)
{
  int a = 0, b = 0;
  cin >> a >> b;
  if (a > b) {
    cout << "a > b" << endl;
  } else if (a < b) {
    cout << "a < b" << endl;
  } else {
    cout << "a == b" << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c;
    cin>>a>>b>>c;
    if(a<=c && c<=b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "<" << #__VA_ARGS__ << ">:", debug_out(__VA_ARGS__)
#define INF LLONG_MAX


int main()
{
  ll k;
  string s;
  cin >> k >> s;
  if (s.size() <= k) cout << s << endl;
  else{
	forll(i, 0, k){
	  cout << s[i];
	}
	cout << "..." << endl;
  }
}


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

int main(){
  int n; cin >> n;
  map<string, int> mp;
  for(int i = 0; i < n; i++){
  	string s; cin >> s;
  	mp[s]++;
  }
  
  int mx = 0;
  for(auto p: mp) mx = max(mx, p.second);
  for(auto p: mp){
  	if(p.second != mx) continue;
  	cout << p.first << endl;
  }
}


Measured memory_bytes: 25216
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextInt() * 1.0;
        double m = sc.nextInt() * 1.0;
        double d = sc.nextInt() * 1.0;
        double c1,c2;
        if(d == 0){
            c1 = n; c2 = 0;
        }else if(d*2 <= n){
            c1 = d*2; c2 = n - d*2;
        }else{
            c1 = (n-d)*2; c2 = 0;
        }
        double ans = (2.0 * c2 + c1) / n / n * (m-1.0);
        System.out.println(ans);
        sc.close();

    }

}


Measured memory_bytes: 21332
n, m = map(int, input().split())
coins = list(map(int, input().split()))
coins.insert(0, 0)
inf = float('inf')
dps = [[inf for _ in range(n + 1)] for _ in range(m + 1)]
# for j in range(n + 1):
#     dps[0][j] = 0
for i in range(m + 1):
    dps[i][0] = 0

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if i == 1:
            dps[i][j] = j // coins[i]
            continue
        if j >= coins[i]:
            dps[i][j] = min(dps[i][j - coins[i]] + 1,
                            dps[i - 1][j - coins[i]] + 1,
                            dps[i - 1][j])
        else:
            dps[i][j] = dps[i - 1][j]
print(dps[m][n])



Measured memory_bytes: 43904
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int n, o, h, t;
    string s;
    cin >> n;
     
    while(n--)
{
        o = h = t = 0;
        while(o < 3)
{
            cin >> s;
            if(s == "HIT")
{
                if(h == 3)
{
                    t++;
                } 
else 
{
                    h++;
                }
            } 
else if(s == "HOMERUN")
{
                t = t + h + 1;
                h = 0;
            } 
else 
{
                o++;
            }
        }
        cout << t << endl;
    }
     
    return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
#define f2(i,j,k) for(int i=j;i>k;i--)
using namespace std;
int main(){
    string s;
    cin>>s;
    while(1){
        s.erase(s.size()-2);
        if(s.substr(0,s.size()/2)==s.substr(s.size()/2)){
            break;
        }
    }
    cout<<s.size()<<endl;
    return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printarray(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define rep(n) for (ll i = 0; i < n; i++)
#define repc(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int fastexpo(int b, int exp){
    if(exp == 0) return 1;
    if(exp == 1) return b;
    int ans = (fastexpo(b,exp/2) % MOD);
    ans *= ans;
    ans %= MOD;
    if(exp % 2 == 1){
        ans *= b;
    }
    ans %= MOD;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin>>n>>k;
    int a[n+2];
    for(int i= 1;i<=n;i++){
    	cin>>a[i];
    }
    int dp[n+2][k+2];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i= 1;i<=n;i++){
    	int pref[k+2];
    	memset(pref, 0, sizeof(pref));
    	for(int j = 0;j<=k;j++){
    		if(j == 0){
    			pref[j] = dp[i-1][j];
    		} else {
    			pref[j] = pref[j-1];
    			pref[j] += (dp[i-1][j]%MOD);
    			pref[j] %= MOD;
    		}
    	}
    	for(int j = 0;j<=k;j++){
    		int val=(pref[j]%MOD);
            int mx=j-a[i]-1;
            if(mx>=0) {
                val=(val-pref[mx]+MOD)%MOD;
            }
            dp[i][j]=val;
    	}
    }
    cout<<dp[n][k]<<endl;
    return 0;
}





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


int main() {
    int a,b,c;
    cin >> a >> b >> c;
    ll sum = 0;
    for(int i = 1;i<=b;i++){
        if((a*i-c)%b == 0){
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,l;
    string st[102];
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        cin>>st[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-i;j++)
        {
            if(st[j]>st[j+1])swap(st[j],st[j+1]);
        }
    for(int i=1;i<=n;i++)
    {
        cout<<st[i];
    }   
    cout<<endl;
    return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

const int MAXN = 100005;

ll n, m, vis[MAXN], dp[MAXN], ans = 0;
vector<ll>adj[MAXN], adj2[MAXN], tarr;

void top_sort(ll node)
{
	vis[node] = true;
	for(auto it : adj[node])
	{
		if(vis[it]) continue;
		top_sort(it);
	}
	tarr.pb(node);
}

ll rec(ll ind)
{
	if(dp[ind] != -1) return dp[ind];
	ll ans = 1;
	for(auto it : adj2[ind])
		ans = max(ans, 1 + rec(it));
	return dp[ind] = ans;
}

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin >> n >> m;
	for(int i=0;i<m;i++)
	{
		ll x, y;
		cin >> x >> y;
		adj[x - 1].pb(y - 1);
		adj2[y - 1].pb(x - 1);
	}
	for(int i=0;i<n;i++)
		if(!vis[i])	
			top_sort(i);
	memset(dp, -1, sizeof(dp));
	for(int i=0;i<n;i++)
		ans = max(ans, rec(tarr[i]) - 1);
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 17400
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
int main(){
  ll n;
  cin >> n;
  double p[n];
  REP(i,n) cin >> p[i];
  double dp[n+1][n+1];
  fill(dp[0],dp[n+1],0.0);
  dp[0][0] = 1.0;
  REP(i,n){
    REP(j,i+1){
      dp[i+1][j] += dp[i][j]*p[i];
      dp[i+1][j+1] += dp[i][j]*(1.0-p[i]);
    }
  }
  double ans = 0.0;
  REP(i,(n+1)/2){
    ans += dp[n][i];
  }
  printf("%.12f\n", ans);
  return 0;
}


Measured memory_bytes: 70528
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
template<class T> void read(T &x) {
	x=0; int f=1,ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=getchar();}
	x*=f;
}
typedef long long ll;
const ll inf=1e18;
const int maxn=80+5;
const int maxm=320+5;
const int maxK=maxn;
const int maxnode=maxn*2+maxK*2;
int N,M;
int st,ed;
int x[maxn],y[maxn]; ll v[maxn];
int Lx[maxK],Ly[maxK],Rx[maxK],Ry[maxK];
char t[maxm]; int a[maxm],b[maxm];
struct edge {
	int to,cap; ll cost; int rev;
	edge(int to=0,int cap=0,ll cost=0,int rev=0):to(to),cap(cap),cost(cost),rev(rev){}
};
vector<edge> adj[maxnode];
inline void addedge(int u,int v,int c,ll w) {
	adj[u].push_back(edge(v,c,w,adj[v].size()));
	adj[v].push_back(edge(u,0,-w,adj[u].size()-1));
}
namespace MCMF {
	ll dis[maxnode]; bool inq[maxnode];
	int prev[maxnode],pree[maxnode];
	bool SPFA() {
		queue<int> q;
		for(int i=st;i<=ed;++i) {
			dis[i]=-inf;
		}
		dis[st]=0;
		inq[st]=1;
		q.push(st);
		while(!q.empty()) {
			int u=q.front(); q.pop();
			inq[u]=0;
			for(unsigned int i=0;i<adj[u].size();++i) {
				edge &e=adj[u][i]; if(!e.cap) continue;
				if(dis[e.to]<dis[u]+e.cost) {
					dis[e.to]=dis[u]+e.cost;
					prev[e.to]=u;
					pree[e.to]=i;
					if(!inq[e.to]) {
						q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		return dis[ed]!=-inf;
	}
	void maxflow(int &flow,ll &cost) {
		while(SPFA()) {
			int delt=1e9;
			for(int u=ed;u!=st;u=prev[u]) {
				edge &e=adj[prev[u]][pree[u]];
				delt=min(delt,e.cap);
			}
			flow+=delt;
			cost+=delt*dis[ed];
			for(int u=ed;u!=st;u=prev[u]) {
				edge &e=adj[prev[u]][pree[u]];
				e.cap-=delt;
				adj[u][e.rev].cap+=delt;
			}
		}
	}
}
ll sol(int K) {
	st=0,ed=K+N+N+K+1;
	for(int i=st;i<=ed;++i) {
		adj[i].clear();
	}
	for(int i=1;i<=K;++i) {
		Lx[i]=Ly[i]=0;
		Rx[i]=Ry[i]=101;
	}
	for(int i=1;i<=M;++i) {
		switch(t[i]) {
			case 'L': Lx[b[i]+1]=a[i]+1; break;
			case 'D': Ly[b[i]+1]=a[i]+1; break;
			case 'R': if(K>b[i]) Rx[K-b[i]]=a[i]-1; break;
			case 'U': if(K>b[i]) Ry[K-b[i]]=a[i]-1; break;
		}
	}
	for(int i=1;i<K;++i) {
		if(Lx[i]>Lx[i+1]) Lx[i+1]=Lx[i];
		if(Ly[i]>Ly[i+1]) Ly[i+1]=Ly[i];
	}
	for(int i=K;i>1;--i) {
		if(Rx[i]<Rx[i-1]) Rx[i-1]=Rx[i];
		if(Ry[i]<Ry[i-1]) Ry[i-1]=Ry[i];
	}
	for(int i=1;i<=K;++i) {
		addedge(st,i,1,0);
		for(int j=1;j<=N;++j) {
			if(x[j]>=Lx[i]&&x[j]<=Rx[i]) {
				addedge(i,K+j,1,0);
			}
			if(y[j]>=Ly[i]&&y[j]<=Ry[i]) {
				addedge(K+N+j,K+N+N+i,1,0);
			}
		}
		addedge(K+N+N+i,ed,1,0);
	}
	for(int i=1;i<=N;++i) {
		addedge(K+i,K+N+i,1,v[i]);
	}
	int flow=0; ll cost=0;
	MCMF::maxflow(flow,cost);
	return flow==K?cost:-inf;
}
int main() {
	read(N);
	for(int i=1;i<=N;++i) {
		read(x[i]),read(y[i]),read(v[i]);
	}
	read(M);
	for(int i=1;i<=M;++i) {
		static char tmp[5];
		scanf("%s",tmp);
		t[i]=tmp[0],read(a[i]),read(b[i]);
	}
	ll an=0;
	for(int i=1;i<=N;++i) {
		an=max(an,sol(i));
	}
	printf("%lld\n",an);
	return 0;
} 

Measured memory_bytes: 1152
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    C, S, F = [], [], []
    for _ in range(N-1):
        c, s, f = LI()
        C.append(c)
        S.append(s)
        F.append(f)
    for i in range(N-1):
        cur_t = 0
        for j in range(i, N-1):
            c, s, f = C[j], S[j], F[j]
            if cur_t > s:
                if cur_t % f == 0:
                    pass
                else:
                    cur_t += (f - cur_t % f)
            else:
                cur_t = s
            cur_t += c
        print(cur_t)
    print(0)
main()



Measured memory_bytes: 66924
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib> 
#include <ctime>
#include <unordered_map>
using namespace std;
typedef long long ll;
int main() {
	string s; int ret;
	cin >> s;
	if (s.compare("SUN") == 0) {
		ret = 7;
	} else if (s.compare("MON") == 0) {
		ret = 6;
	}
	else if (s.compare("TUE") == 0) {
		ret = 5;
	}
	else if (s.compare("WED") == 0) {
		ret = 4;
	}
	else if (s.compare("THU") == 0) {
		ret = 3;
	}
	else if (s.compare("FRI") == 0) {
		ret = 2;
	}
	else {
		ret = 1;
	}
	cout << ret << endl;
}

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

int main(){
    string s;
    cin >> s;
    int count = 0;
    for (int i = 0; i < 4; i++) {
        if (s.at(i) == '2') {
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    T = [ tuple( map( int, input().split())) for _ in range(N)]
    T = sorted(T,key=lambda x:x[1])
    time = 0
    ans = "Yes"
    for i in range(N):
        time += T[i][0]
        if time > T[i][1]:
            ans = "No"
            break
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 33480
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

vector<vector<int>> pos;
int N;

int f[2][2020][2020];

int main(){
  cin >> N;
  pos.resize(2,vector<int>(N));
  rep(i,0,N * 2 - 1){
    char c;
    int x;
    cin >> c >> x;
    x--;
    int y = c == 'W';
    pos[y][x] = i;
  }

  rep(i,0,1){
    rep(j,0,N - 1){
      rep(k,j + 1,N - 1){
        f[i][j][N] += (pos[i][k] < pos[i][j]);
      }
      for(int k = N - 1;k >= 0;k--){
        f[i][j][k] = f[i][j][k + 1] + (pos[1 - i][k] < pos[i][j]);
      }
    }
  }


  vector<vector<int>> dp(N + 1,vector<int>(N + 1,1e9));
  dp[0][0] = 0;
  rep(i,0,N){
    rep(j,0,N){
      if(i < N) dp[i + 1][j] = min(dp[i + 1][j] , dp[i][j] + f[0][i][j]);
      if(j < N) dp[i][j + 1] = min(dp[i][j + 1],dp[i][j] + f[1][j][i]);
    }
  }
  cout << dp[N][N] << endl;
}

Measured memory_bytes: 47744
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto&& i : a){
        cin >> i;
    }
    sort(rbegin(a), rend(a));
    if(a[0] < accumulate(begin(a) + 1, end(a), 0)){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
}

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

#define ln '\n'
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    static const double pi = acos(-1);
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double theta = 30 * h + 0.5 * m - 6 * m;
    double ans = sqrt(a * a + b * b - 2 * a * b * cos(theta * pi / 180));
    cout << fixed << setprecision(20) << ans << ln;
    return 0;
}


Measured memory_bytes: 4204
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m){
        if(n == 0 && m == 0){
            break;
        }
        vector<pair<int, int>> l(m, pair<int, int>(0,0));
        for(int i = 0;i<m;i++){
            l[i].second = i+1;
        }
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                int temp;
                cin >> temp;
                if(temp == 1){
                    l[j].first += 1;
                }
            }
        }
        for(int i = 0;i<m;i++){
            l[i].first = m+1-l[i].first;
        }
        sort(l.begin(), l.end());
        for(int i = 0;i<l.size()-1;i++){
            cout << l[i].second << " ";
        }
        cout << l[l.size()-1].second << endl;
    }
    return 0;
}

Measured memory_bytes: 2996