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

using namespace std;

struct blk {
  long long w, s, v;
};


bool mysort(const blk& a, const blk& b) {
  if (a.w < b.w && a.s <= b.s) return true;
  if (a.w == b.w && a.s <= b.s) return true;
  if (a.w < b.w && a.s == b.s) return true;

  auto x = min(a.s, b.s-a.w);
  auto y = min(b.s, a.s-b.w);

  if (x > y) return true;
  if (x == y && a.s < b.s) return true;
  if (x == y && a.w < b.w) return true;
  return false;
}

vector<vector < long long > > F( 1000+10, vector<long long>(10000+10, 0));

int main() {
  long long N;
  cin >> N;

  vector<blk> lst(N);
  long long naxs= 1;
  for (long long i=0; i < N; i++) {
    long long mys;
    cin >> lst[i].w >> mys >> lst[i].v;
    lst[i].s = mys;
    naxs = max(naxs, mys);
  }

  stable_sort(lst.begin(), lst.end(), mysort);
  reverse(lst.begin(), lst.end());
  // for(auto i=0; i<N;i++) printf("%d %d %d\n", lst[i].w, lst[i].s, lst[i].v);
  // F[i, s],  blk 0..i, with solid s

  F[0][ lst[0].s ] = lst[0].v;

  for(long long i=1; i< N; i++) {
    long long is = lst[i].s;
    for(long long s=0; s<=naxs; s++) { F[i][s] = F[i-1][s]; }

    for(long long s=0; s<=is; s++) {
      long long a = 0;

      if (s + lst[i].w <= naxs) { a = F[i-1][s + lst[i].w ]; }

      F[i][s] = max( F[i][s],  a + lst[i].v);
    }

    // s == is
    for(auto s=is; s<=naxs; s++) {
      long long a=0;
      if (s + lst[i].w <= naxs) { a = F[i-1][s + lst[i].w ]; } 
      F[i][is] = max( F[i][is], a  + lst[i].v);
    }
  }

  long long ans = -1;
  for(long long i=0; i< N; i++) {
    for(long long s=0; s<=naxs; s++) ans = max(ans, F[i][s]);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 79360
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 1))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload :cl-debug-print))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * simple-bit-vector) make-prime-table))
(defun make-prime-table (size)
  "Erzeugt die Primzahlentabelle 0 zu SIZE-1."
  (declare (optimize (speed 3) (safety 1)))
  (let ((dict (make-array size :element-type 'bit :initial-element 1)))
    (setf (aref dict 0) 0 (aref dict 1) 0)
    (loop for even-num from 4 below size by 2
          do (setf (aref dict even-num) 0))
    (loop for p from 3 to (ceiling (sqrt size)) by 2
          when (= 1 (aref dict p))
          do (loop for composite from (+ p p) below size by p
                   until (>= composite size)
                   do (setf (aref dict composite) 0)))
    dict))

(defun decompose-to-pow-table (num prime-table)
  (declare (optimize (speed 3) (safety 1))
           ((unsigned-byte 63) num) ; Beachte!
           ((simple-array bit (*)) prime-table))
  (let ((factor-table (make-array (length prime-table)
                                  :element-type '(unsigned-byte 7)
                                  :initial-element 0)))
    (when (= 1 (aref prime-table 2))
      (setf (aref factor-table 2)
            (loop while (evenp num)
                  count t
                  do (setf num (ash num -1)))))
    (loop for prime from 3 to (min num (- (length prime-table) 1)) by 2
          when (= 1 (aref prime-table prime))
          do (setf (aref factor-table prime)
                   (loop with quot and rem
                         do (setf (values quot rem) (floor num prime))
                         while (zerop rem)
                         count t
                         do (setf num quot)))
          finally (return factor-table))))

(defmacro println (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))

;; Hauptteil

;; Sei gcd(a1, ..., aN) = 2^f(2)*3^f(3)*....
;; Da P = a1* ... *aN, gilt gcd(a1, ..., aN)^N | P und somit
;; 2^(f(2)*N)*3^(f(3)*N)*... | P
;; Wir müssen nur so ein f finden, so dass jedes f(k) maximal ist.
;; Nun sei 2^g(2)*3^g(3)*.... die Primfaktorzerlegung von P.
;; Dann muss f Folgendes erfüllen:
;; f(2)* N <= g(2)
;; f(3)* N <= g(3)...

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (p (read))
         (size 100001)
         (prime-dict (make-prime-table size))
         (factor-table (decompose-to-pow-table p prime-dict)))
    (declare (fixnum n p)
             ((simple-array (unsigned-byte 7) (*)) factor-table))
    (if (= n 1)
        (println p)
        (loop for prime from 2 below size
              with product of-type integer = 1
              when (>= (aref factor-table prime) 1)
              do (setf product
                       (* product (expt prime (floor (aref factor-table prime) n))))
              finally (println product)))))

#-swank(main)


Measured memory_bytes: 14948
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define mod 1000000007
using namespace std;

void dfile(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


int32_t main()
{   
    //dfile();
    
    int dp[100005]={};
    int n,k;
    cin>>n>>k;
    int h[n];
    for(int i=0;i<n;i++) cin>>h[i];
    dp[0]=0;
    dp[1]=abs(h[0]-h[1]);

    for(int i=2;i<n;i++){
        int op1=INT_MAX;
        for(int j=1;j<=k;j++){
            if((i-j)>=0){
                op1=min(op1,dp[i-j]+abs(h[i]-h[i-j]));
            }
        }
        dp[i]=op1;
    }
    cout<<dp[n-1];
    // for(int i=0;i<n;i++) cout<<dp[i]<<" ";

    return 0;   
}

// int op1=dp[i-1]+abs(h[i]-h[i-1]);
//         int op2=dp[i-2]+abs(h[i]-h[i-2]);
//         dp[i]=min(op1,op2);

Measured memory_bytes: 5120
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)

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

using namespace std;
using ll = long long int;
using lc = complex<double>;

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    constexpr double PI = acos(-1);
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<tuple<ll,ll>> p(n);
    for(ll i=0; i<n; i++) {
        ll x, y;
        cin >> x >> y;
        p[i] = {x, y};
    }

    ll res = 0;
    {
        ll mx = -1e9, mi = 1e9;
        for(ll i=0; i<n; i++) {
            auto [x, y] = p[i];
            mx = max(mx, x+y);
            mi = min(mi, x+y);
        }
        res = max(res, (mx-mi));
    }
    {
        ll mx = -1e9, mi = 1e9;
        for(ll i=0; i<n; i++) {
            auto [x, y] = p[i];
            mx = max(mx, x-y);
            mi = min(mi, x-y);
        }
        res = max(res, (mx-mi));
    }
    cout << res << endl;
}

Measured memory_bytes: 6360
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp =[[float("inf")] * (n+1) for _ in range(m+1)]
dp[0][0] = 0

for i in range(m):
    for j in range(n+1):
        if j >= c[i]:
            dp[i+1][j] = min(dp[i+1][j-c[i]] + 1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[m][n])



Measured memory_bytes: 43736
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
ll lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    string S, T;
    cin >> S >> T;
    sort(S.begin(), S.end());
    sort(T.begin(),T.end());
    reverse(T.begin(),T.end());

    if (S < T)
    {
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    LL N;cin >> N;
    vector<LL> a(N);
    rep(i,N)cin >> a[i];
    int ans = 0;
    int num = 1;
    rep(i,N){
        if(a[i] == num){
            num++;
            ans++;
        }
    }
    ans = N-ans;
    if(ans == N)ans = -1;
    cout << ans << endl;
}


Measured memory_bytes: 1792
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
from math import ceil
ans = []
for a in range(X):
    for b in range(min(Y,ceil(3000/(a+1)))):
        for c in range(min(Z,ceil(3000/(a+1)/(b+1)))):
            ans.append(A[a]+B[b]+C[c])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
ll sz(string &s){ return (ll)s.size(); }
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }

int main(){
    ll n,q;
    cin >> n >> q;
    dsu d(n);

    ll t,u,v;
    rep(i,0,q){
        cin >> t >> u >> v;
        if(t == 0){
            d.merge(u,v);
        }
        else{
            cout << d.same(u,v) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4052
k = int(input())
while k < 2 or k > 100:
    k = int(input())

evenNum = []
oddNum = []

for o in range(1, k+1, 2):
    oddNum.append(o)

for e in range(2, k+1, 2):
    evenNum.append(e)

ways = len(evenNum) * len(oddNum)
print(ways)

Measured memory_bytes: 3064
#include <algorithm>
#include<iostream>
#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<queue>
#include<functional>
#include<cmath>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
using namespace std;
using ll = long long;
using P = pair<int, int>;
using graph = vector<vector<int>>;
int main() {
	queue<ll> q;
	int K; cin >> K;
	rep(i, 9) {
		q.push(i+1);
	}
	rep(j,K-1) {
	    long long int a = q.front(); q.pop(); 
		if (a % 10 == 0) {
			q.push(10 * a );
			q.push(10 * a + 1);
		}
		else if (a % 10 == 9) {
			q.push(10 * a + 8);
			q.push(10 * a + 9);
		}
		else {
			rep(i, 3) {
				q.push(10 * a+(a%10)+i-1);
			}
		}
	}
	cout << q.front() << endl;
}


	


		






Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	string s;
	cin >> s;

	if (s == "SSS") {
		cout << 0 << endl;
		return 0;
	}
	if (s == "RRR") {
		cout << 3 << endl;
		return 0;
	}
	if ((s[0] == 'R' && s[1] == 'R') || (s[2] == 'R' && s[1] == 'R')) {
		cout << 2 << endl;
		return 0;
	}
	cout << 1 << endl;
}


Measured memory_bytes: 3620
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
    int N;
    cin >> N;
    string ans = "Yes";
    int t[N],x[N],y[N];
    int j,k,l;
    for(int i=1;i<=N;i++){
        cin >> t[i] >> x[i] >> y[i];
        if(i == 1){
            j = t[1];
            k = abs(x[1]);
            l = abs(y[1]);
            if( ((j+k+l)%2 != 0) || (j <  (k + l)) ){
                ans = "No";
                break;
            }
        }
        if(i > 1){
            j = abs(t[i-1] - t[i]);
            k = abs(x[i-1] - x[i]);
            l = abs(y[i-1] - y[i]);
            if(j >= k + l){
                if((j+k+l)%2 != 0){
                    ans = "No";
                    break;
                }
            }else{
                ans = "No";
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0, xxx_rep_end = (n); i < xxx_rep_end; ++i)
#define all(x) (x).begin(), (x).end()

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

constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;
constexpr ll mod = 1000000007;

int main() {
    ll N;
    cin >> N;

    ll ans = 0;
    for (ll i = 1; i <= N; ++i) {
        if (i % 3 == 0 || i % 5 == 0) continue;
        ans += i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3676
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

count = 0
for a in A:
    result = C
    for i, b in zip(a, B):
        result += i * b
    if result > 0:
        count += 1

print(count)

Measured memory_bytes: 3060
// in the name of Allah

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define ll long long
#define double long double
#define sz(x) ((int) (x.size()))

#define fr first
#define se second

#define inf 1e9
#define max_n 123456
#define mod 1000000007

ll add(ll a, ll b) {
	a += b;
	if(a >= mod) return a - mod;
	return a;
}

ll mul(ll a, ll b) {
	a *= b;
	if(a >= mod) return a % mod;
	return a;
}

ll power(ll a, ll b) {
	ll p = 1;
	while(b) {
		if(b&1) p = mul(p, a);
		a = mul(a, a);
		b /= 2;
	}
	return p;
}

int n, k;
ll a[101];
ll dp[101][100001];

ll sum(int idx, int l, int r) {
	if(l < 0) l = 0;
	ll res = dp[idx][r];
	if(l > 0) res = add(res, mod - dp[idx][l-1]);
	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; i++) cin >> a[i];
	memset(dp, 0, sizeof dp);
	for(int i=0; i<=a[0]; i++) dp[0][i] = 1;
	for(int i=1; i<n; i++) {
		for(int j=1; j<=k; j++) dp[i-1][j] = add(dp[i-1][j], dp[i-1][j-1]);
		for(int j=0; j<=k; j++) dp[i][j] = sum(i-1, j-a[i], j);
	}
	cout << dp[n-1][k] << endl;
	return 0;
}

Measured memory_bytes: 79232
#include <iostream>
using namespace std;
int main(void){
    int n;
    long long int a[10001]={0}; //100001個
    cin >> n;
    for(int i=0; i<n; i++){
       cin >> a[i];
    }
    long long int min=1000000,max=-1000000,sum=0;
    for(int i=0; i<n; i++){
        if(a[i]<min){
            min=a[i];
        }
        if(a[i]>max){
            max=a[i];
        }
        sum=sum+a[i];
    }
    cout << min << " " << max << " " << sum << endl;
}   




Measured memory_bytes: 3184
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	N := nextInt()
	count := 0
	for i := 1; i <= N; i++ {
		a := nextInt()
		if i%2 == 1 && a%2 == 1 {
			count++
		}
	}
	fmt.Fprintf(out, "%d\n", count)
}


Measured memory_bytes: 1808
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		
		
		if (a == 2 && b == 2) {
			System.out.println("Yes");
		} else if ((a == 4 || a == 6 || a == 9 || a == 11) && (b == 4 || b == 6 || b == 9 || b == 11)) {
			System.out.println("Yes");
		} else if ((a != 4 && a != 6 && a != 9 && a != 11 && a != 2) && (b != 4 && b != 6 && b != 9 && b != 11 && b != 2)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, a, b;
    cin >> n >> a >> b;
    if (a > b || (n == 1 && a != b)) cout << 0 << endl;
    else cout << (b - a) * (n - 2) + 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INF = 999999999;
const int MOD = (int)1e9 + 7;
const int EPS = 1e-9;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int price = 700;
  REP(i,3){
      if (S[i]=='o')price+=100;
  }
  cout << price << endl;
}

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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define fork(i, n) for (ll i = 0; i < (n); i++)
#define forn for (ll i = 0; i < (n); i++)
#define fori(i, k, n) for (ll i = k; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);

template <typename A, typename B>
inline void chmin(A &a, B b)
{
	if (a > b)
		a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b)
{
	if (a < b)
		a = b;
}
template <typename T>
void print(vector<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(deque<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(vector<vector<T>> &a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}
const int mxN = 1e7;
ll a[mxN + 1] = {};

void findDivisors(int n)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j * i <= n; j++)
			a[i * j]++;
	}
}

int main()
{
	fast;
	ll n, ans = 0;
	cin >> n;
	findDivisors(n);
	for (ll i = 1; i <= n; i++)
	{
		ans += i * a[i];
	}
	cout << ans << en;
}

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

int main(){
    long long n,m;
    cin>>n>>m;
    if(n*m%2==0&&m!=1&&n!=1)cout<<n*m/2;
    else if(m!=1&&n!=1)cout<<n*m/2+1;
    else cout<<1;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
int dp[53][53][53][53][3][2];
int x,y,a[53],b[53];
int cal(int x,int y,int t){
	int res=0;
	if(t)while(y>x){
		if(a[y]!=-1)res+=a[y],y--;
	    else y--;}
	else while(y>x){
		if(b[y]!=-1)res+=b[y],y--;
	     else y--;}
	return res;
}
int dfs(int a1,int a2,int b1,int b2,int pass,int turn,int sum){
	if(pass==3)return sum;
	if(dp[a1][a2][b1][b2][pass][turn]!=1e15)return sum+dp[a1][a2][b1][b2][pass][turn];
	int res;
	if(turn){
		res=-1e14;
		if(a1!=0){
		  if(a[a1]==-1)res=max(res,dfs(a1-1,a2,b1,b1,0,turn^1,sum));
		  else res=max(res,dfs(a1-1,a2,b1,b2,0,turn^1,sum));
		}
		res=max(res,dfs(a1,a1,b1,b1,pass+1,turn^1,sum+cal(a1,a2,1)-cal(b1,b2,0)));
	}
	else{
		res=1e14;
		if(b1!=0){
		  if(b[b1]==-1)res=min(res,dfs(a1,a1,b1-1,b2,0,turn^1,sum));
		  else res=min(res,dfs(a1,a2,b1-1,b2,0,turn^1,sum));
		}
		res=min(res,dfs(a1,a1,b1,b1,pass+1,turn^1,sum+cal(a1,a2,1)-cal(b1,b2,0)));
	}
	dp[a1][a2][b1][b2][pass][turn]=res-sum;
	return res;
}
main(){
	r(i1,53)r(i2,53)r(i3,53)r(i4,53)r(i5,3)r(i6,2)dp[i1][i2][i3][i4][i5][i6]=1e15;
	cin>>x>>y;
	r(i,x)cin>>a[x-i];
	r(i,y)cin>>b[y-i];
	cout<<dfs(x,x,y,y,0,1,0)<<endl;
}

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



struct P
{
    int x,y,z;

    bool operator<(const P &a)const{

        if(x!=a.x) return x>a.x;
        return y>a.y;
    }

};

vector<int> v;

//bitset<4001000> b;
int i,n,d,m,k,a,b,c;

int o[311][333];
int l[1];
int j[1];
int e;


//int dx[10]={2,2,-2,-2,1,1,-1,-1},dy[10]={1,-1,1,-1,2,-2,2,-2};

int dx[10]={0,1,0,-1,1,1,-1,-1},dy[10]={1,0,-1,0,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
long long mod=1000000009,mod2=1000000009,mod3=2017;
long long x,z,y;
double pi=3.14159265;
P u[1];
stack<int> s;
//set<int> se;
//priority_queue<int> q;
//queue<int> q;
//string r,r1;
char r[1111];
//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p;
/*
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<long long, int, custom_hash> safe_map;
*/
//list<int> l;


//deque<int> de;
//srand((int)time(NULL));




bool as(P a,P b)
{
    if(a.x!=b.x)
       return a.x>b.x;
    return a.y<b.y;


}

int main()
{
    scanf("%d",&a);
    for(int t=1;t<=3;t++)
    {
        scanf("%s",r+1);
        for(int t=1;t<=a;t++)
            o[r[t]][t]++;
    }
    for(int t=1;t<=a;t++)
    {
        n=0;
        for(int w='a';w<='z';w++)
            n=max(n,o[w][t]);
        k+=n;
    }
    printf("%d",a*3-k);
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int const INF = 1001001001;


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

int a,b,c;
cin >> a >> b >> c;
int x = abs(a-b), y = abs(b-c), z = abs(c-a);

int ans = x + y + z -max(x,max(y,z));
cout << ans << endl;

return 0;
}

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

namespace Competitive
{
    internal class Solution
    {
        public int N, M;
        public int[] A;
        public long MOD = 1000000007;

        public void Run()
        {
            {
                var line = Input.ReadIntArray();
                N = line[0];
                M = line[1];
            }

            A = new int[N + 1];
            for (int i = 0; i < M; i++)
            {
                A[Input.ReadInt()] = 1;
            }

            long[] dp = new long[N + 1];
            dp[0] = 1;

            for (int i = 1; i <= N; i++)
            {
                if (A[i] == 1) continue;
                dp[i] += (i < 1 ? 0 : dp[i - 1]);
                dp[i] += (i < 2 ? 0 : dp[i - 2]);
                dp[i] %= MOD;
            }

            Console.WriteLine(dp[N]);

        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 14304
//
//  main.cpp
//  CoderProj
//
//  Created by Minoru Hayashi on 2020/05/02.
//  Copyright © 2020 Minoru Hayashi. All rights reserved.
//
//  ABC165
//
//

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for (int i=0; i<(n); i++)
#define REP2(i,x,n) for (int i=x; i<(n); i++)
#define ALL(n) begin(n), end(n)

using ll = long long;

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

// const ll INF = 1LL<<60;
// const int INF = 1<<29;
// const int MOD = 1000000007;
//#define __DBG__


void solve(void){
  
  ll X;
  cin >> X;
  
  ll n=100;
  ll y=0;
  
  while(n<X){
    n=n*1.01;
    y++;
  }
  cout << y << endl;
  return;
}



#define TESTCASES 1

int main() {


    cin.tie(0);
    ios::sync_with_stdio(false);

    REP(i,TESTCASES){
      solve();
    }
 
    return 0;
}



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

int main () {
  int N;
  cin >> N;
  vector<char> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
  }
  string ans ="Three";
  for (int i = 0; i < N; i++) {
    if (S.at(i) == 'Y') {
      ans = "Four";
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;

int n,res=0;
int a[200005];

int quick_power(int a,int b)
{
	if (b==0)  return 1;
	
	int res=1;
	for (;b;b=b>>1,a=(a*a)%mod)
	{
		if (b&1)  res=(res*a)%mod;
	}
	return res;
}

bool cmp(int a,int b)
{
	return a>b;
}

signed main()
{
    cin>>n;
    for (int i=1;i<=n;i++)  cin>>a[i];
 	
 	sort(a+1,a+n+1,cmp);
 
    int tmp3=quick_power(2,n*2-2);
    int tmp2=(tmp3*2)%mod;
    int res=0;
 
    for (int i=1;i<=n;i++)
    {
        int tmp=(tmp2*a[i])%mod;
        res=(res+tmp)%mod;
        tmp2=(tmp2+tmp3)%mod;
    }
    cout<<res<<endl;
    
    return 0;
}

Measured memory_bytes: 1792
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;



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

	cin >> N;
	vector<string>s(N);
	vector<int>v(N);
	for (int i = 0; i < N; i++) {
		cin >> s[i] >> v[i];
	}
	string t;
	cin >> t;
	long long int ans = 0;
	for (int i = 0; i < N; i++) {
		if (s[i] == t) {
			for (int j = i + 1; j < N; j++) {
				ans += v[j];
			}
			cout << ans << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
/*
CODED BY               
**************
DARSHAN JAIN
darshanjain31
**************
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define MOD 1000000007
 
int main()
{ 
	string s;
	cin>>s;
	char prev=s[s.size()-1];
		string final;
	if(prev=='?')
	{
		final.pb('D');
		prev='D';
	}
	else
		final.pb(s[s.size()-1]);
	for (int i = s.size()-2; i>=0; i--)
	{
		if(s[i]=='?')
		{
			//cout<<s[i]<<endl;
			if(prev=='D'&&s[i-1]!='P')
			{
				final.pb('P');
				prev='P';
			}
			else
			{
				final.pb('D');
				prev='D';
			}
		}
		else
		{
			final.pb(s[i]);
			prev=s[i];
		}
	//cout<<final<<endl;
	}
	for (int i =final.size()-1; i>=0 ; i--)
	{
		cout<<final[i];
	}
	cout<<endl;
}

Measured memory_bytes: 3860
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#define rep(i,N) for(int i=0; i<N;i++)
using namespace std;

int main(){
    int N;
    cin>>N;
    vector<int> x(N),y(N);
    rep(i,N){
        cin>>x[i]>>y[i];
    }
    vector<int> arr(N);
    rep(i,N){
        arr[i]=i;
    }
    double d=0.0;
    int count=0;
    do {
        rep(i,N-1){
            d+=sqrt(pow(x[arr[i+1]]-x[arr[i]],2)+pow(y[arr[i+1]]-y[arr[i]],2));
        }
        count++;
    } while (next_permutation(arr.begin(), arr.end()));
    d/=count;

    cout <<fixed<<setprecision(12)<<d<<endl;
    return 0;
}



Measured memory_bytes: 256
A = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'
A = A.split(', ')
print(A[int(input()) - 1])

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

int di[] = {-1, 0, 1, 0};
int dj[] = {0, -1, 0, 1};
int m, n;

bool check(int ci, int cj) { return ci >= 0 && cj >= 0 && ci < m && cj < n; }

int main() {
    cin >> m >> n;
    string s[m];
    for (int i = 0; i < m; i++) cin >> s[i];
    int ans = 0;
    while (true) {
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '.') {
                    pii alp[50];
                    for (int k = 0; k < 50; k++) alp[k] = pii(-1, -1);
                    for (int k = 0; k < 4; k++) {
                        int ci = i, cj = j;
                        while (check(ci, cj) && s[ci][cj] == '.') {
                            ci += di[k];
                            cj += dj[k];
                        }
                        if (check(ci, cj)) {
                            int c = s[ci][cj] - 'A';
                            if (alp[c].first != -1) {
                                pii cur = alp[c];
                                s[ci][cj] = '.';
                                s[cur.first][cur.second] = '.';
                                ret += 2;
                            } else {
                                alp[c] = pii(ci, cj);
                            }
                        }
                    }
                }
            }
        }
        if (ret == 0) break;
        ans += ret;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int now = 0;
    for (auto &&i : a)
    {
        cin >> i;
        if (now + 1 == i)
        {
            now++;
        }
    }
    if (now == 0)
    {
        now = n + 1;
    }
    cout << n - now << "\n";
}

Measured memory_bytes: 1024
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ON			1										// 汎用フラグ - ON
#define D_OFF			0										// 汎用フラグ - OFF
#define D_CHAR_MAX		30005									// 最大文字数

// 内部変数
static FILE *szpFpI;											// 入力
static char sc1Str[D_CHAR_MAX];									// 文字列
static int siCCnt;												// 文字数
static int si1Num[10];											// １文字
static int si2Num[10][10];										// ２文字
static int si3Num[10][10][10];									// ３文字

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i, j, k;
	char lc1Buf[1024];

	// 文字数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &siCCnt);

	// 文字列 - 取得
	fgets(sc1Str, sizeof(sc1Str), szpFpI);

	// 各文字チェック
	for (i = 0; i < siCCnt; i++) {
		int liNum = sc1Str[i] - '0';

		// ２文字 -> ３文字
		for (j = 0; j < 10; j++) {
			for (k = 0; k < 10; k++) {
				if (si2Num[j][k] == D_ON) {
					si3Num[j][k][liNum] = D_ON;
				}
			}
		}

		// １文字 -> ２文字
		for (j = 0; j < 10; j++) {
			if (si1Num[j] == D_ON) {
				si2Num[j][liNum] = D_ON;
			}
		}

		// １文字
		si1Num[liNum] = D_ON;
	}

	// ３文字の種類数 - 取得
	int liCnt = 0;
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 10; j++) {
			for (k = 0; k < 10; k++) {
				if (si3Num[i][j][k] == D_ON) {
					liCnt++;
				}
			}
		}
	}

	return liCnt;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	memset(si1Num, 0, sizeof(si1Num));							// １文字
	memset(si2Num, 0, sizeof(si2Num));							// ２文字
	memset(si3Num, 0, sizeof(si3Num));							// ３文字

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	sprintf(lc1Buf, "%d\n", liRet);
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
typedef long long ll;
const int M = 1e9 + 7;
const int INF = 1e9;
const int MAX = 1e5 + 5;
const int MAX_V = 1e3 + 5;

// adjecent-list
struct Edge {
    int to;
    int weight;
};
vector<Edge> Graph[MAX];
bool checked[MAX];
int color[MAX];

typedef pair<int, int> P;        // (cst, to)
typedef tuple<int, int, int> P3; // (x_pos, y_pos, index)
vector<P> G[MAX];
bool used[MAX];

int prim() {
    priority_queue<P, vector<P>, greater<P>> que;
    memset(used, 0, sizeof(used));
    que.push(P(0, 0));
    int ret = 0;
    while (!que.empty()) {
        int cst = que.top().first, v = que.top().second;
        que.pop();
        if (used[v]) continue;
        used[v] = 1;
        ret += cst;
        for (int i = 0; i < G[v].size(); i++)
            que.push(P(G[v][i].first, G[v][i].second));
    }
    return ret;
}

bool comPair1(const P3 &firstElof, const P3 &secondElof) {
    return get<0>(firstElof) < get<0>(secondElof);
}

bool comPair2(const P3 &firstElof, const P3 &secondElof) {
    return get<1>(firstElof) < get<1>(secondElof);
}

int main() {
    int n;
    cin >> n;
    vector<P3> pos;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        pos.push_back(P3(x, y, i));
    }
    int res = 0;
    vector<P3> x_sort_pos = pos;
    sort(x_sort_pos.begin(), x_sort_pos.end(), comPair1);
    vector<P3> y_sort_pos = pos;
    sort(y_sort_pos.begin(), y_sort_pos.end(), comPair2);
    for (int i = 0; i < n - 1; i++) {
        int x_cost, y_cost;
        P3 prev_x = x_sort_pos[i], prev_y = y_sort_pos[i];
        P3 now_x = x_sort_pos[i + 1], now_y = y_sort_pos[i + 1];
        x_cost = get<0>(now_x) - get<0>(prev_x);
        y_cost = get<1>(now_y) - get<1>(prev_y);
        G[get<2>(prev_x)].push_back(P(x_cost, get<2>(now_x)));
        G[get<2>(now_x)].push_back(P(x_cost, get<2>(prev_x)));
        G[get<2>(prev_y)].push_back(P(y_cost, get<2>(now_y)));
        G[get<2>(now_y)].push_back(P(y_cost, get<2>(prev_y)));
    }
    cout << prim() << endl;
}


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

vector<vector<int>> G(105, vector<int>(105, INT32_MAX / 2)), J = G;
int N, M;

int main() {
	cin >> N >> M;
	int a, b, c;
	vector<tuple<int, int, int>> E(M);
	for (int i = 0;i < M;i++) {
		cin >> a >> b >> c;
		G[a][b] = c;
		G[b][a] = c;
		J[a][b] = c;
		J[b][a] = c;
		E[i] = make_tuple(a, b, c);
	}

	for (int i = 1;i <= N;i++)
		J[i][i] = 0;

	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= N;j++) {
			for (int k = 1;k <= N;k++) {
				J[j][k] = min(J[j][i] + J[i][k], J[j][k]);
			}
		}
	}

	int cnt, ans = M;
	for (int i = 0;i < M;i++) {
		cnt = 0;
		tie(a, b, c) = E[i];
		for (int j = 1;j <= N;j++) {
			for (int k = 1;k <= N;k++) {
				if (J[j][a] + J[b][k] + c == J[j][k]) {
					cnt = 1;
				}
			}
		}
		
		ans -= cnt;
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define ll long long
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
const long double pi = acos(-1.0);
const double eps = 1e-9;
using namespace std;

const int N = 3000 + 1;
ll dp[N][N][4], a[N][N];
int r, c, k;
void solve(){
    cin >> r >> c >> k;
    
    for (int i = 1; i <= k; i++){
        int posr, posc, v;
        cin >> posr >> posc >> v;
        a[posr][posc] = v;
    }
    dp[1][1][1] = a[1][1];
    
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            if (i == j && i == 1) continue;
            
            for (int k = 0; k <= 3; k++){
                dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
                if (k + 1 <= 3) dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j - 1][k] + a[i][j]);
            }
            for (int k = 0; k <= 3; k++){
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k]);
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][k] + a[i][j]);
            }
        }
    }
    ll ans = 0;
    for (int k = 0; k <= 3; k++) ans = max(ans, dp[r][c][k]);
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(6);
    //freopen("input.txt", "r", stdin);   
    //freopen("sausage.in","r",stdin); freopen("sausage.out", "w", stdout);
    int step;
    step = 1;
    //cin >> step;
    for (int i = 1; i <= step; i++){
         solve();
    }
}


Measured memory_bytes: 355180
#include<bits/stdc++.h>
using namespace std;
int n,k;
int p[5555],c[5555];
bool used[5555];
vector<long long> S;
void dfs(int i,long long s)
{
	if(used[i])
		return ;
	used[i]=true;
	s+=c[i];
	S.push_back(s);
	dfs(p[i],s);
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>p[i];
		p[i]--;
	}
	for(int i=0;i<n;i++)
		cin>>c[i];
	long long ans=-1e18;
	for(int i=0;i<n;i++){
		memset(used,false,sizeof(used));
		dfs(i,0);
		if(S.back()>0&&k>=S.size()){
			long long q=k/S.size();
			if(q>=1){
				long long mx=-1e18;
				if(q>1)
					mx=0;
				for(int i=0;i<S.size();i++)
					mx=max(mx,S[i]);
				ans=max(ans,(q-1)*S.back()+mx);
			}
			
			{ 
				int r=k%S.size();
				long long mx=0;
				for(int i=0;i<r;i++)
					mx=max(mx,S[i]);
				ans=max(ans,q*S.back()+mx);
			} 
		}
		else{
			for(int j=1;j<=k;j++){
				if(j-1<S.size())
					ans=max(ans,S[j-1]);
				else
					break;
			}
		}
		S.clear();
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3952
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine()) - 1;

		int count = 0;
		while (n > 0) {
			n /= 3;
			count++;
		}
		System.out.println(count);
	}
}



Measured memory_bytes: 24336
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
using ll = long long;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
// vector<vector<ll>> vec(100000,vector<ll>(3,0));
vector<ll> vec;
// ll gcd(ll x,ll y){
//   if(y == 0){return x;}
//   return gcd(y,x%y);
// }
void modi(ll x){
  for(ll i=1;i<=sqrt(x);i++){
    if(x % i == 0){
      vec.push_back(i);
      vec.push_back(x/i);
    }
  }
}

int main(){
  ll n,k;
  ll tmp;
  cin >> n >> k;
  ll a[n];
  ll sum = 0;
  rep(i,n){
    cin >> a[i];
    sum += a[i];
  }
  ll maximum = sum;
  modi(maximum);
  sort(all(vec),greater<ll>());
  ll ans;
  ll diff;
  vector<ll> pres(n);
  for(auto itr:vec){
    diff=0;
    ll up=0,down=0;
    rep(i,n){
      tmp = a[i] % itr;
      pres[i] = tmp;
      up += tmp;
    }
    sort(all(pres));
    rep(i,n){
      if(up == down){
        break;
      }else{
        up -= pres[n-1-i];
        down += itr - pres[n-1-i];
      }
    }
    // MSG(itr);
    // MSG(up);
    if(up <= k){
      ans = itr;
      break;
    }
  }
  cout << ans;
}


Measured memory_bytes: 256
#[derive(Clone, Copy)]
pub struct Edge {
	pub to: usize,
	pub capacity: i64,
	pub reverse: usize,
}

pub struct Dinic {
	edges: Vec<Vec<Edge>>,
	level: Vec<i64>,
	iter: Vec<usize>,
}

impl Dinic {
	pub fn new(v: usize) -> Self {
		Dinic { edges: vec![vec![]; v], level: vec![0; v], iter: vec![0; v] }
	}

	pub fn add_edge(&mut self, from: usize, to: usize, capacity: i64) {
		let reverse = self.edges[to].len();
		self.edges[from].push(Edge { to: to, capacity: capacity, reverse: reverse });
		let reverse = self.edges[from].len() - 1;
		self.edges[to].push(Edge { to: from, capacity: 0, reverse: reverse });
	}

	fn bfs(&mut self, from: usize) {
		for i in self.level.iter_mut() {
			*i = -1;
		}
		let mut q = std::collections::VecDeque::new();
		self.level[from] = 0;
		q.push_back(from);
		while let Some(v) = q.pop_front() {
			for e in self.edges[v].iter() {
				if e.capacity > 0 && self.level[e.to] < 0 {
					self.level[e.to] = self.level[v] + 1;
					q.push_back(e.to);
				}
			}
		}
	}

	fn dfs(&mut self, v: usize, to: usize, f: i64) -> i64 {
		if v == to {
			return f;
		}
		while self.iter[v] < self.edges[v].len() {
			let i = self.iter[v];
			let e = self.edges[v][i];
			if e.capacity > 0 && self.level[v] < self.level[e.to] {
				let d = self.dfs(e.to, to, std::cmp::min(f, e.capacity));
				if d > 0 {
					self.edges[v][i].capacity -= d;
					self.edges[e.to][e.reverse].capacity += d;
					return d;
				}
			}
			self.iter[v] += 1;
		}
		0
	}

	fn max_flow(&mut self, from: usize, to: usize) -> i64 {
		let mut flow = 0;
		loop {
			self.bfs(from);
			if self.level[to] < 0 {
				break;
			}
			for i in self.iter.iter_mut() {
				*i = 0;
			}
			loop {
				let f = self.dfs(from, to, std::i64::MAX);
				if f > 0 {
					flow += f;
				} else {
					break;
				}
			}
		}
		flow
	}
}

fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	let mut dinic = Dinic::new(2 * n + 2);
	let red = (0..n).map(|_| (s.next().unwrap().parse::<u8>().unwrap(), s.next().unwrap().parse::<u8>().unwrap())).collect::<Vec<_>>();
	let blue = (0..n).map(|_| (s.next().unwrap().parse::<u8>().unwrap(), s.next().unwrap().parse::<u8>().unwrap())).collect::<Vec<_>>();
	let from = 2 * n;
	let to = 2 * n + 1;
	for i in 0..n {
		dinic.add_edge(from, i, 1);
		dinic.add_edge(n + i, to, 1);
		for j in 0..n {
			if red[i].0 < blue[j].0 && red[i].1 < blue[j].1 {
				dinic.add_edge(i, n + j, 1);
			}
		}
	}
	let ans = dinic.max_flow(from, to);
	println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[4][110],a[4][110];
int main(){
    int n;
    cin>>n;
    for (int i=1;i<=2;i++){
        for (int j=1;j<=n;j++) cin>>a[i][j];
    }
    dp[1][1]=a[1][1];
    for (int i=1;i<=2;i++){
        for (int j=1;j<=n;j++){
            if (i==1&&j==1) continue;
            if (i==1) dp[i][j]=dp[i][j-1]+a[i][j];
            else if (j==1) dp[i][j]=dp[i-1][j]+a[i][j];
            else dp[i][j]=max(dp[i][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
        }
    }
    cout<<dp[2][n];
    cout<<endl;
}


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

static const int INF = (1 << 28);

int main() {
    string A;
    cin >> A;

    int N = A.size();
    vector<int> indexes[26];

    for (int i = 0; i < N; i++) {
        indexes[A[i] - 'a'].push_back(i + 1);
    }
    for (int i = 0; i < 26; i++) {
        indexes[i].push_back(N + 1);
    }

    vector<int> table(N + 2, INF);  // A_[i,N]に含まれない最小の部分列の長さ(iは1-indexed)
    table[N + 1] = 0;

    for (int i = N; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            int idx = *upper_bound(indexes[j].begin(), indexes[j].end(), i);
            table[i] = min(table[i], table[idx] + 1);
        }
    }

    int idx = 0;
    string ans = "";
    while (idx != N + 1) {
        int nidx = -1;
        char ch;

        for (int i = 0; i < 26; i++) {
            int foo = *upper_bound(indexes[i].begin(), indexes[i].end(), idx);
            if (nidx < 0 or table[nidx] > table[foo]) {
                nidx = foo;
                ch = char('a' + i);
            }
        }
        idx = nidx;
        ans.push_back(ch);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2308
#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

int main() {
	while (true) {
		int coin = 0;
		int price = 0;

		cin >> price;
		if (price == 0) {
			break;
		}

		price = 1000 - price;

		for (auto temp : { 500, 100, 50, 10, 5, 1 }) {
			const auto temp_div = div(price, temp);
			coin += temp_div.quot;
			price = temp_div.rem;
		}

		cout << coin << endl;
	}
	return 0;
}

Measured memory_bytes: 3004