akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>
#include<functional>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;
const long long ll_max = 9223372036854775807;
const long long ll_min = -9223372036854775807;
const int int_max = 2147483647;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> ret;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			ret[i] ++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}



// 繰り返し二乗法
ll pow2(ll n, ll p, ll mod) {
	if (p == 0 || n == 1) {
		return 1;
	}
	else {
		ll ret = pow2(n * n % mod, p / 2, mod);
		if (p % 2 == 1) {
			ret *= n;
		}
		return ret % mod;
	}
}


#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)


int main() {
	const ll mod = 1e9 + 7;
	ll N;
	cin >> N;
	vll sum(N+1,0);

	repeq(i, 1, N) {
		ll A;
		cin >> A;
		sum[i] = (sum[i - 1] + A)%mod;
	}

	ll ans = 0;
	repeq(i, 1, N) {
		ll a = sum[i] - sum[i - 1];
		if (a < 0) {
			a += mod;
		}
		ll b = sum[N] - sum[i];
		if (b < 0) {
			b += mod;
		}
		ans += (a * b) % mod;
		ans %= mod;
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4840
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	int a[4];
	for(int i = 0; i < 4; i++)
	{
		a[i] = n % 10;
		n /= 10;
	}
	
	if((a[0] == a[1] && a[1] == a[2])
	|| (a[1] == a[2] && a[2] == a[3]))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
object Main {

  class UnionFind(val n: Int) {
    private[this] val par = Array.range(0, n)

    def root(x: Int): Int =
      if(par(x) == x) x else { par(x) = root(par(x)); par(x) }

    def same(x: Int, y: Int): Boolean = root(x) == root(y)
    def unite(x: Int, y: Int): Unit = par(root(x)) = root(y)
  }

  def main(args: Array[String]): Unit = {

    val Array(n,q,_*) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
    val uf = new UnionFind(n)

    for(i <- 1 to q){
      val Array(com,x,y,_*) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
      if(com==0)uf.unite(x,y)
      else println(if(uf.same(x,y)) 1 else 0)
    }

  }

}

Measured memory_bytes: 80296
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()
#define pb push_back

typedef long long ll;
const int inf = 1e9+7;
const ll infll = 1 << 60LL;
const ll mod = 1e9 + 7;
// 0~3までは左右前後 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

// 型による変数のオーバーフローに気をつけろ！！
// 悩んだら図やグラフを書け！！悩む前から書け！！

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

	int r;
	cin >> r;

	if (r < 1200) {
		cout << "ABC" << endl;
		return 0;
	}
	else if (r < 2800) {
		cout << "ARC" << endl;
		return 0;
	}
	else {
		cout << "AGC" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a>(b&&c)&&(a==(b+c)))
    {
        printf("Yes");
    }
    else if((b>(a&&c)&&(b==(a+c))))
    {
        printf("Yes");
    }
    else if((c>(b&&a)&&(c==(b+a))))
            {
                printf("Yes");
            }
            else
                {
                    printf("No");
                }
    return 0;
}


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

int main(){
    string S;
    cin >> S;
    int N = S.length();
    // get step to be elgotic in the graph (Ergodic hypothesis)
    vector<int> change(N,0);
    char prev = 'R';
    int count = 0;
    int converge = 0;
    int non_connected = 0;
    rep(i,N){
        if( S[i] == prev ) ++count;
        else{
            converge = max(count,converge);
            count = 1;
            prev = S[i];
            change[non_connected] = i;
            non_connected += 1;
        }
    }
    change.erase( change.begin() + non_connected, change.end() ); // start: R, end: L => len(change) is odd
    cout << endl;
    vector<int> vout(N,0);
    for( int i=0; i<int(change.size()); i+=2 ){
        int prv = 0;
        if( i > 0 ) prv = change[i-1];
        int now = change[i];
        int nxt = N;
        if( i < change.size()-1 ) nxt = change[i+1];
        vout[now-1] = (now -prv)/2 + (nxt -now)/2 + (now -prv)%2;
        vout[now] = (now -prv)/2 + (nxt -now)/2 + (nxt-now)%2;
    }
   for( int n : vout ) cout << n << endl;
    return 0;
}

Measured memory_bytes: 4300
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solve{
    static void Main(string[] args){
        var N = int.Parse(Console.ReadLine());
        var P = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var Q = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int a = 1, b = 1;
        var list = new List<int>(8);
        for (int i = 0; i < N; i++){ 
            var pi = P[i];
            var x = pi - list.Where(d => d < pi).Count();
            a += i == N - 1 ? 0 : (x - 1) * Factorial(N - 1 - i);
            list.Add(pi);}
        list.Clear();
        for (int i = 0; i < N; i++){
            var qi = Q[i];
            var x = qi - list.Where(d => d < qi).Count();
            b += i == N - 1 ? 0 : (x - 1) * Factorial(N - 1 - i);
            list.Add(qi);}
        var answer = Math.Abs(a - b);
        var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();}

    public static int Factorial(int n){
        int result = 1;
        for (int i = n; i > 1; i--){
            result *= i;}
        return result;}}

Measured memory_bytes: 28284
import java.util.*;

class Main{

    public static void main(String[] args){

	Scanner sc = new Scanner(System.in);

	int M = sc.nextInt();

	int D = sc.nextInt();

	int ans = 0;

	for(int j=1; j<=M; j++){

	for(int i=1; i<=D; i++){

	int k = i/10;

	if(k>=2 && k*(i-10*k)==j && (i-10*k)>=2){

	ans++;

    }
 
   }
  }

	System.out.println(ans);

 }
}

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

//strcmp : compare function

int main(void) {
	int n;
	char str[200000][11];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%s", str[i]);
	qsort(str, n, 11, strcmp);
	int count[200000];
    for (int i = 0; i < n; i++)
        count[i] = 0;
	for (int i = 0; i < n - 1; i++)
		if (strcmp(str[i], str[i + 1])==0) {
			count[i]++;
			count[i + 1] += count[i];
			count[i + 1]++;
		}
	int max = 0;
	for (int i = 0; i < n; i++)
		if (count[i] > max)
		max = count[i];

	for (int i = 0; i < n; i++)
		if (count[i] == max)
			printf("%s\n", str[i]);
	return 0;
}


Measured memory_bytes: 4988
n,m = (int(x) for x in input().split())
A = [input().split() for i in range(n)]
b = [int(input()) for i in range(m)]

for i in range(n):
    x = 0
    for j in range(m):
        x += int(A[i][j]) *b[j]
    print(x)


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

#define ll long long

template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

signed main() {
  ll a, b;
  char op;
  cin >> a >> op >> b;
  if(op=='+') drop(a+b);
  cout << a-b << endl; 

  return 0;
}


Measured memory_bytes: 3584
import itertools
n = int(input())
s = []
for i in range(n):
    s.append(int(input()))
s.sort()
if sum(s) % 10 != 0:
    print(sum(s))
else:
    for i in range(n):
        if s[i] % 10 != 0:
            print(sum(s) - s[i])
            exit()
    print(0)

Measured memory_bytes: 3060
from collections import Counter

n = int(input())

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

c = Counter(s).most_common()


m = c[0][1]

ans = []

for i in range(len(c)):
    if c[i][1] == m:
        ans.append(c[i][0])

ans.sort()

for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 45036
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    surplus_scores = []
    sum_lack_score = 0
    ans = 0
    for a, b in zip(A, B):
        if a > b:
            surplus_scores.append(a - b)
        elif a < b:
            sum_lack_score += b - a
            ans += 1

    if sum_lack_score > 0:
        surplus_scores.sort(reverse=True)
        pass_exam = False
        for score in surplus_scores:
            sum_lack_score -= score
            ans += 1
            if sum_lack_score <= 0:
                pass_exam = True
                break
        if not pass_exam:
            ans = -1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 18420
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N;
    vector< pair <ll, ll> > task;
    cin>>N;
    ll a, b, TimeMaxima;
    rep(i, N){
        cin>>a>>b;
        TimeMaxima=max(TimeMaxima, b);
        task.push_back({b, a});
    }
    rep(i, N){
        task[i].first=TimeMaxima-task[i].first;
    }
    sort(all(task));
    ll Timecount=0;
    rep(i, N){
        if(Timecount<task[i].first) Timecount=task[i].first;
        Timecount+=task[i].second;
    }
    cout<<(Timecount>TimeMaxima ? "No" : "Yes" )<<endl;
    return 0;
}

Measured memory_bytes: 6512
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, b, c;
    cin >> a >> b >> c;
    
    cout << (float)a * b / 2 << endl;
    
    return 0;
}

Measured memory_bytes: 256
array = gets.split.map(&:to_i)
string = gets.chomp
if array[1] == 1
  hoge = string[0].downcase + string[array[1]...array[0]]
elsif array[0] == array[1]
  hoge = string[0...array[0]-1] + string[array[0]-1].downcase
else
  hoge = string[0...array[1]-1] + string[array[1]-1].downcase + string[array[1]...array[0]]
end
puts hoge

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    char ara[10000],ara2[100000];
    int a,b,c,i,j,k,n;
    cin>>n;
    getchar();
    for (i=0;i<n;i++,printf ("\n"))
    {
        scanf("%[^\n]",ara);
        getchar();
        for (j=0;ara[j]!='\0';j++)
        {
            if (ara[j]=='o')
                if (ara[j-5]=='o' && ara[j-4]=='s' && ara[j-3]=='h' && ara[j-2]=='i' && ara[j-1]=='n' && ara[j-6]=='H')
            {
                ara[j]='a';
            }

        }
        printf ("%s",ara);
    }
}


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

const double EPS = 1e-8;
const double INF = 1e12;
const double PI = acos(-1);

using Point = complex<double>;
using Polygon = vector<Point>;

inline int sgn(const double &a) { return (a < -EPS ? -1 : (a > EPS ? 1 : 0)); }

inline bool eq(const Point &a, const Point &b) { return abs(a - b) < EPS; }

namespace std {
inline bool operator<(const Point &a, const Point &b) {
    if (sgn(a.real() - b.real()))
        return sgn(a.real() - b.real()) < 0;
    return sgn(a.imag() - b.imag()) < 0;
}
} // namespace std

double dot(const Point &a, const Point &b) { return real(conj(a) * b); }

double det(const Point &a, const Point &b) { return imag(conj(a) * b); }

struct Line {
    Point p1, p2;

    Line(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {}

    bool operator<(const Line &rhs) const {
        if (eq(p2, rhs.p2))
            return p1 < rhs.p1;
        return p2 < rhs.p2;
    }
    bool operator==(const Line &rhs) const {
        return (eq(p1, rhs.p1) && eq(p2, rhs.p2)) ||
               (eq(p1, rhs.p2) && eq(p2, rhs.p1));
    }
};

enum CCW {
    ONLINE_FRONT = -2,
    CLOCKWISE,
    ON_SEGMENT,
    COUNTER_CLOCKWISE,
    ONLINE_BACK
};

int ccw(Point p0, Point p1, Point p2) {
    Point a = p1 - p0;
    Point b = p2 - p0;
    if (sgn(det(a, b)) == 1)
        return COUNTER_CLOCKWISE;
    if (sgn(det(a, b)) == -1)
        return CLOCKWISE;
    if (sgn(dot(a, b)) == -1)
        return ONLINE_BACK;
    if (sgn(norm(b) - norm(a)) == 1)
        return ONLINE_FRONT;
    return ON_SEGMENT;
}

inline Point curr(const Polygon &p, const int &i){
    return p[i % p.size()];
}

inline Point next(const Polygon &p, const int &i){
    return p[(i+1) % p.size()];
}

inline Point prev(const Polygon &p, const int &i){
    return p[(i+p.size()-1) % p.size()];
}

bool is_convex(const Polygon &poly){
    if(poly.size() < 3)return false;
    if(poly.size() == 3)return true;
    int r = 0;
    for(int i=0;i<poly.size();i++){
        int c = ccw(prev(poly, i), curr(poly, i), next(poly, i));
        if(r == 0 && abs(c) == 1)r = c;
        if(c != ONLINE_FRONT && c*r != 1)return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    Polygon pg;
    for(int i=0;i<n;++i){
        double x, y;
        cin >> x >> y;
        Point p = Point(x, y);
        pg.push_back(p);
    }
    cout << (is_convex(pg) ? 1 : 0) << endl;

    return 0;
}



Measured memory_bytes: 3288
N = int(input())
s = sorted(["".join(sorted((input()))) for i in range(N)])
count = 0

num=1
for i in range(N-1):
    if(s[i]==s[i+1]):
        num += 1
    elif(num>1):
        count += num*(num-1)/2
        num = 1
    
if(num>1):
    count += num*(num-1)/2
print(int(count))

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

long long n, x, ans, odd[11], even[11];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(long long i = 0 ; i < n && cin >> x ; i++)
        if(x%2) odd[i] = 1, even[i] = 2;
        else odd[i] = 2, even[i] = 1;
    for(long long i = 0 ; i < (1<<n) ; i++){
        vector <long long> cur;
        for(long long j = 0 ; j < n ; j++)
            if((1<<j)&i) cur.push_back(1);
            else cur.push_back(0);
        long long sum = 0;
        for(long long j : cur) sum += j;
        if(sum == n) continue;
        long long cnt = 1;
        for(long long j = 0 ; j < cur.size() ; j++)
            if(cur[j]) cnt *= odd[j];
            else cnt *= even[j];
        ans += cnt;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


    class Program
    {
        static void Main(string[] args)
        {
            string[] Input = Console.ReadLine().Split(' ');
            int X = int.Parse(Input[0]);
            int N = int.Parse(Input[1]);
            if(N > 0){
            string[] Input2 = Console.ReadLine().Split(' ');
            
            var list = new List<int>();
            foreach(var i in Input2){
                list.Add(int.Parse(i));
            }
            list.Sort();
            
            int min = X;
            int max = X + 1;
            
            for(int i = 0; i < list.Count; i++){
                if(max == list[i]){
                    max++;
                }
            }
            
            for(int i = list.Count - 1; i >= 0; i--){
                if(min == list[i]){
                    min--;
            }
            }
            int a = Math.Abs(X - max);
            int b = Math.Abs(X - min);
            if(a < b){
            Console.WriteLine(max);
            }else
            {
                Console.WriteLine(min);
            }
            }else{
                Console.WriteLine(X);
            }
        }
    }

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

using namespace std;

long long ans, x, n;
map<int, int> m;

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> x;
		m[x]++;
	}
	
	for(auto itr = m.begin(); itr != m.end(); itr++) ans += itr->second - itr->first * (itr->first<=itr->second?1:0);

	cout << ans << endl;
}

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

#define int long long

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n, k, res = 0;
	cin >> n >> k;

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

	sort(a.begin(), a.end());

	for (int i = 0; i < k; ++i)
		res += a[i];

	cout << res;

	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left, int mid, int right) {
  int n1 = mid -left;
  int n2 = right - mid;
// C++forループ専用のint型を宣言できる
// ループの中のみ有効なので安全
  for(int i=0;i<n1;i++) L[i] = A[left + i];
  for(int i=0;i<n2;i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i=0, j=0;
  for(int k=left; k<right; k++) {
    cnt++;
    if(L[i]<=R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right) {
  if(left+1 < right) {
    int mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int main(void) {
  int A[MAX], n, i;
  cnt = 0;

	cin >> n; // scanf("%d",&n);
  for(i=0;i<n;i++) cin >> A[i];

  mergeSort(A, n, 0, n);
  for(i=0;i<n;i++) {
    if(i)cout<<" ";
  	cout << A[i]; //printf("%d",A[i]);
  }
  cout << endl; // endlは改行

  cout << cnt << endl; // printf("\n");

  return 0;
}


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

using namespace std;
unsigned long long f(unsigned long long a) {
     unsigned long long res[] = {a,1,a+1,0};
     return res[a & 3];
}

unsigned long long getXor(unsigned long long a, unsigned long long b) {
     return f(b)^f(a-1);
}
int main() 
{
	unsigned long long a, b ;
	cin >> a >> b;
	cout << getXor(a,b) << endl;
    return 0;
} 

Measured memory_bytes: 256
def f(n):
    return 3 * n + 1 if n % 2 else n / 2
a = int(input())
li = set([a])
ans = 1
while True:
    ans += 1
    a = f(a)
    if a in li:
        break
    else:
        li.add(a)

print(ans)

Measured memory_bytes: 38256
#include <iostream>
using namespace std;
int main(){
	int N;
	cin >> N;
	int t, x, y, i;
	for(i=0;i<N;i++){
		cin >> t >> x >> y;
		if( ( x + y > t ) || ( ( x + y ) % 2 != t % 2 ) ){
			cout << "No" << endl;
			return 0;
		} 
	}
	cout << "Yes" << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    map<string, bool> A1, A2, A3;

    int N;
    cin >> N;
    string S;
    cin >> S;

    A1[S.substr(N-1, 1)] = true;
    A1[S.substr(N-2, 1)] = true;
    A2[S.substr(N-2)] = true;
    for (int i = N - 3; i >= 0; i--) {
        for (auto const& e : A2) {
            string s = S.substr(i, 1);
            s += e.first;
            A3[s] = true;
        }

        for (auto const& e : A1) {
            string s = S.substr(i, 1);
            s += e.first;
            A2[s] = true;
        }

        A1[S.substr(i, 1)] = true;
    }
    
    cout << A3.size() << endl;
}

Measured memory_bytes: 3716
#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
#define INF 1000000
#define LINF 1000000000000LL
using namespace std;
typedef pair<long long,int> P;
long long a[4000];
vector<P> dp[4001];
int r[4000];
vector<int> pos;
int max(int a,int b){return a>b?a:b;}

int main(){
	int n,i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%lld",&a[i]);
	dp[0].push_back(P(-LINF,0));
	for(i=0;i<n;i++){
		int m=dp[i].size();
		sort(dp[i].begin(),dp[i].end());
		r[0]=-INF;
		for(j=1;j<=m;j++)r[j]=max(r[j-1],dp[i][j-1].second);
		long long s=0;
		for(j=i+1;j<=n;j++){
			s+=a[j-1];
			int p=lower_bound(dp[i].begin(),dp[i].end(),P(s,0))-dp[i].begin();
			dp[j].push_back(P(s,r[p]+1));
		}
	}
	P ans=P(0,-INF);
	for(i=0;i<dp[n].size();i++)if(ans.second<dp[n][i].second)ans=dp[n][i];
	printf("%d\n",ans.second);
	int p=n;
	int t=ans.second;
	while(t>0){
		long long s=0;
		while(1){
			p--;
			s+=a[p];
			for(i=0;i<dp[p].size();i++)if(dp[p][i].first<s&&dp[p][i].second==t-1)break;
			if(i<dp[p].size())break;
		}
		if(p>0)pos.push_back(p);
		t--;
	}
	reverse(pos.begin(),pos.end());
	for(i=0;i<pos.size();i++)printf("%d ",pos[i]);
	puts("");
	return 0;
}

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

using namespace std;

using ll = long long;

bool f[1000001];

int main()
{
  int s;
  cin >> s;
  for (int i = 1; i <= 1000000; ++i)
  {
    if (f[s])
    {
      cout << i << endl;
      return 0;
    }
    else
    {
      f[s] = true;
      if (s & 1)
      {
        s *= 3;
        s++;
      }
      else
      {
        s /= 2;
      }
    }
  }
}


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

int main()
{
	int num;
	int an[5];
	bool yay = true;

	for(int i = 0; i < 5; i++){
		cin >> an[i];
	}

	cin >> num;

	if( an[4] - an[0] > num ){
		yay = false;
	}


	if( yay == false ){
		cout << ":(" << endl;
	} else {
		cout << "Yay!" << endl;
	}

	return 0;
}

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

#pragma region Macro
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v) sort(v.begin(), v.end())
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define vvi vector<vector<int>>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#pragma endregion

// 入力
int N, M, Q;
vvi num_list;
vi temp;

void make_list(int ind, int min){
	if(ind == N){
		num_list.eb(temp);
		/*
		rep(j,temp.size()){
			cout << temp[j];
		}
		cout << "\n";
		*/
		return;
	}
	else{
		FOR(i, min, M+1){
			temp[ind] = i;
			make_list(ind + 1, i);
		}
	}
	return;
}

void solve(){
	#define int ll
	// ここに処理を記述
	// コンパイル時はエイリアス「gpp」--> c++17でコンパイル
	
	cin >> N >> M >> Q;
	temp.resize(N);

	vi a(Q), b(Q), c(Q), d(Q); 
	rep(i,Q){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--;
		b[i]--;
	}

	make_list(0, 1);

	int ans = 0;
	rep(i, num_list.size()){
		int ans_temp = 0;
		rep(j, Q){
			if(num_list[i][b[j]] - num_list[i][a[j]] == c[j]){
				ans_temp += d[j];
			}
		}
		chmax(ans, ans_temp);
	}

	cout << ans << endl;

}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	
	solve();
	return 0;
}

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

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }
//
int main(){
	string s ; cin >> s; 

	string odd="RUD", even="LUD"; 

	for(int i = 0 ; i <(int)s.length() ; i++ ){
		if( ((i+1)&1 && find(all(odd),s[i])==odd.end())||
				( (i+1)%2==0 && find(all(even),s[i])== even.end() )){
			cout << "No" << endl; 
			return 0;
		}
	}
	cout << "Yes"<<endl; 
}


Measured memory_bytes: 256
use petgraph::algo::dijkstra;
use petgraph::graph::{Graph, NodeIndex};
use proconio::input;
use std::cmp::min;

const MAX_A: usize = 50;
fn main() {
    input! {
        n: usize,
        m: usize,
        s: usize,
        uvab: [(usize, usize, usize, usize); m],
        cd: [(usize, usize); n],
    }
    let max_silver = MAX_A * (n - 1);
    let mut g = Graph::<(usize, usize), usize>::new();
    let nodes: Vec<Vec<NodeIndex>> = (0..n)
        .map(|c| (0..=max_silver).map(|s| g.add_node((c, s))).collect())
        .collect();
    for s in 0..=max_silver {
        for &(u, v, a, b) in &uvab {
            if a <= s {
                g.add_edge(nodes[u - 1][s], nodes[v - 1][s - a], b);
                g.add_edge(nodes[v - 1][s], nodes[u - 1][s - a], b);
            }
        }
    }
    for s in 0..=max_silver {
        for (u, &(c, d)) in cd.iter().enumerate() {
            g.add_edge(nodes[u][s], nodes[u][min(s.wrapping_add(c), max_silver)], d);
        }
    }
    let shortest_path_time = dijkstra(&g, nodes[0][min(s, max_silver)], None, |e| *e.weight());
    for silvers in nodes.iter().skip(1) {
        let min = silvers
            .iter()
            .min_by_key(|s| shortest_path_time[s])
            .unwrap();
        println!("{}", shortest_path_time[min]);
    }
}


Measured memory_bytes: 27768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define RI(a) scanf("%d",&a)
#define RII(a,b) scanf("%d%d",&a,&b)
#define RIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll mod=ll(1e9+7);



int main()
{
	//IOS;
	string s;
	cin>>s;
	int n=s.length();
	int i=n/2;
	char cur=s[n/2];
	if(n%2==0&&s[n/2]!=s[n/2-1]){
		cout<<n/2;
		return 0;
	}
	while(i<n&&s[i]==s[n-1-i]&&s[i]==cur) i++;
	cout<<i;

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll a,b;cin>>a>>b;
    cout<<a*b<<"\n";
}


Measured memory_bytes: 3640
N = int(input())

cnt = [[0] * 10 for i in range(10)]

# 先頭がi,末尾がjの数字のカウント : cnt[i][j]

for i in range(1,N+1):
    s = str(i)
    head = int(s[0])
    tail = int(s[-1])
    cnt[head][tail] += 1
# print(cnt)
ans = 0
for i in range(10):
    for j in range(10):
        ans += cnt[i][j] * cnt[j][i]

print(ans)

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

const int maxn = 1e5+100;

bool can[maxn];
int cnt[maxn];

int n,m;

int main()
{
  //  freopen("./test.txt","r",stdin);
    scanf("%d %d",&n,&m);

    memset(can,0,sizeof(can));
    can[1] = 1;
    for(int i = 1;i <= n;++i)
        cnt[i] = 1;
    for(int i = 0;i < m;++i)
    {
        int a,b;
        scanf("%d %d",&a,&b);

        if(can[a])
        {
            can[b] = 1;

        }
        cnt[a]--;
        cnt[b]++;
        if(cnt[a] == 0)
            can[a] = 0;
    }

    int res = 0;
    for(int i = 1;i <= n;++i)
        if(can[i])
            res++;

    printf("%d\n",res);

    return 0;
}



Measured memory_bytes: 768
n, x = map(int, input().split())


def p(level):
    if level == 0:
        return 1
    return 2*p(level-1)+1


def a(level):
    if level == 0:
        return 1
    return 2*a(level-1)+3


def f(level, x):
    if level == 0:
        return 1
    elif x == 1:
        return 0
    else:
        if 1 < x <= 1 + a(level-1):
            return f(level-1, x-1)
        else:
            if x == 2 + a(level-1):
                return 1 + p(level-1)
            elif 2+a(level-1) < x <= 2 + 2*a(level-1):
                return 1 + p(level-1)+f(level-1, x-2-a(level-1))
            elif x == 3 + 2*a(level-1):
                return 1 + 2*p(level-1)


print(f(n, x))

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
N,K = map(int, input().split())
bi = []
i = 1
j = 0
while i < K:
    bi.append(i)
    i *= 2
    j += 1
bi.append(i)
ans = max(0,N-K+1)
ite = min(N+1,K)

for i in range(1,ite):
    # print(i,j, bi[j-1] * i)
    if j > 0 and bi[j-1] * i >= K:
        j -= 1
    #print(i, j, i*bi[j])
    ans += 0.5**j
print('{:.10f}'.format(ans / N))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
        using namespace std;
        #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
        #define M_PI 3.14159265358979323846
        #define data data_
        #define ff first
        #define ss second
        #define pb push_back
        #define ld long double
        #define int long long
        #define print(t) cout << "Case #" << t << ": ";
        int32_t main()
        {
            tani_nachi_ke  
            
            
            int n;
            cin >> n;
            map<string,int> mp;
            for(int i = 0; i < n; i++)
            {
                string s;
                cin >>  s;
                mp[s]++;
            }

            cout << "AC" << " x " << mp["AC"] << '\n';
            cout << "WA" << " x " << mp["WA"] << '\n'; 
            cout << "TLE" << " x " << mp["TLE"] << '\n'; 
            cout << "RE" << " x " << mp["RE"] << '\n'; 




           return 0;
        }
          

Measured memory_bytes: 3664
s = int(input())
a = [s]

i = 0
flag = 0
while(True):
    if a[i] % 2 == 0:
        new_a = int(a[i] / 2)
    else:
        new_a = int(3 * a[i] + 1)
    i += 1
    for ai in a:
        if new_a == ai:
            flag = 1
            break
    if flag == 1:
        break
    else:
        a.append(new_a)

print(i + 1)


Measured memory_bytes: 3060
import java.util.*;
import java.io.*;
import static java.lang.System.*;

class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;
  private boolean hasNextByte() {
      if (ptr < buflen) {
          return true;
      }else{
          ptr = 0;
          try {
              buflen = in.read(buffer);
          } catch (IOException e) {
              e.printStackTrace();
          }
          if (buflen <= 0) {
              return false;
          }
      }
      return true;
  }
  private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
  private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
  public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
  public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while(isPrintableChar(b)) {
          sb.appendCodePoint(b);
          b = readByte();
      }
      return sb.toString();
  }
  public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
          minus = true;
          b = readByte();
      }
      if (b < '0' || '9' < b) {
          throw new NumberFormatException();
      }
      while(true){
          if ('0' <= b && b <= '9') {
              n *= 10;
              n += b - '0';
          }else if(b == -1 || !isPrintableChar(b)){
              return minus ? -n : n;
          }else{
              throw new NumberFormatException();
          }
          b = readByte();
      }
  }
  public int nextInt() {
      long nl = nextLong();
      if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
      return (int) nl;
  }
  public double nextDouble() { return Double.parseDouble(next());}
}

class Main {
  public static final int MOD = 1000000007;
  public static final int INF = 1000000000;
  public static void main(String[] args) {
    FastScanner sc = new FastScanner();
    int N = sc.nextInt();
    int time[][] = new int[N][2];
    for(int i=0; i<N; i++){
      time[i][0] = sc.nextInt();
      time[i][1] = sc.nextInt();
    }
    Arrays.sort(time, (a,b) -> Integer.compare(a[1], b[1]) );
    int sum = 0;
    boolean check = true;
    for(int i=0; i<N; i++){
      sum += time[i][0];
      if(sum > time[i][1]){
        check = false;
        break;
      }
    }
    if(check == true) out.println("Yes");
    else out.println("No");
  }

  public static int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
  }
}

Measured memory_bytes: 41260
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int n=s.size();
	if(s[n-1]=='s'){
		s+="es";
	}else {
		s+='s';
	}
	cout<<s<<endl;
	return 0;
}

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

Measured memory_bytes: 3624
#include <stdio.h>
 
int main() {
    int m, f, r;
    while (scanf("%d%d%d", &m, &f, &r) == 3 && (~m || ~f || ~r)) {
        if (m == -1 || f == -1) {
            printf("F\n");
        } else if (m + f >= 80) {
            printf("A\n");
        } else if (m + f >= 65) {
            printf("B\n");
        } else if (m + f >= 50 || m + f >= 30 && r >= 50) {
            printf("C\n");
        } else if (m + f >= 30) {
            printf("D\n");
        } else {
            printf("F\n");
        }
    }
    return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; 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

#include <bits/stdc++.h>
#define rep(i,a,n) for(ll i = a;i < n;i++)
typedef long long ll;
using namespace std;

ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}

int main(){ 
    ll n,k;
    cin >> n >> k;

    cout << min(n % k, abs(k - n%k)) << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define INF 900000000

using namespace std;

int n, k, c[5010], r[5010], cost[5010];
vector<int> road[5010];
vector<pair<int, int>> adj[5010];
bool done[5010];

void bfs(int num)
{
	queue<pair<int, int>> que;
	que.push({num,0});
	while (!que.empty())
	{
		int a = que.front().first;
		int b = que.front().second;
		que.pop();
		if (done[a]) continue;
		done[a] = true;
		for (auto u : road[a])
		{
			if (!done[u] && b+1<=r[num])
            {
                adj[num].push_back({ u, c[num]});
                que.push({ u, b + 1 });
            }
		}
	}
}

int dijkstra ()
{
    for (int i=0; i<5010; i++) cost[i]=INF;
    cost[1]=0;
    priority_queue<pair<int, int>> que;
    memset(done, false, sizeof(done));
    que.push({0,1});
    while (!que.empty())
    {
        int a=que.top().second;
        que.pop();
        if (done[a]) continue;
        done[a]=true;
        for (auto u : adj[a])
        {
            int b=u.first, w=u.second;
            if (cost[b]>cost[a]+w)
            {
                cost[b]=cost[a]+w;
                que.push({-cost[b], b});
            }
        }
    }
    return cost[n];
}

int main()
{
    int a,b;
    cin>>n>>k;
    memset(done, false, sizeof(false));
    for (int i=1; i<=n; i++) cin>>c[i]>>r[i];
    for (int i=0; i<k; i++)
    {
        cin>>a>>b;
        road[a].push_back(b);
        road[b].push_back(a);
    }
    for (int i=1; i<=n; i++)
    {
        memset(done ,false , sizeof(done));
        bfs(i);
    }
    cout<<dijkstra()<<'\n';
    return 0;
}



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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))

#define INF (int)1e9+7

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

typedef long long ll;

using namespace std;

int main()
{
    int n;
    int x;
    int dist[100005] = {};

    cin >> n >> x;

    rep(i, n){
        int in;
        cin >> in;
        dist[i] = abs(x - in);
    } 
    
    int ans = 0;
    rep(i, n){
        ans = __gcd(ans, dist[i]); 
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());

		if(N == 3 || N == 5 || N == 7) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}

	}

}


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

ll gcd(ll x, ll y);
int fac(ll n, vector<int> num);

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

const int INF = 1001001001;

//mint�p�̒萔 (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    int n, w;
    cin >> n >> w;
    vector<vector<ll> > wv(n, vector<ll> (2));
    rep(i, n)rep(j, 2) cin >> wv[i][j];

    vector<vector<ll> > dp(n + 1, vector<ll> (w + 1));
    rep(i, n) {
        rep(j, w + 1) {
            if (j >= wv[i][0]) chmax(dp[i + 1][j], dp[i][j - wv[i][0]] + wv[i][1]);
            chmax(dp[i + 1][j], dp[i][j]);
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
ll gcd(ll x, ll y) {
    ll num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

/*�f��������*/
//���색�C�u����
int fac(ll n, vector<int> num) {
    ll kazu = n;
    for (int i = 2; i <= sqrt(n); i++) {
        while (1) {
            if (kazu % i != 0) break;

            kazu /= i;
            num[i]++;
        }
    }
    if (kazu == n && n != 1) return 1;
    int ans = 0;
    if (kazu != 1) ans++;
    for (int i = 2; i <= sqrt(n); i++) {
        for (int j = 1; j <= num[i]; j++) {
            num[i] -= j;
            ans++;
        }
    }
    return ans;
}

Measured memory_bytes: 83116
#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 rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    string s[H];
    rep(i, H) cin >> s[i];
    int ans = inf;
    //横に切るのを全探索
    rep(i, (1<<(H-1))){
        vector<int> v;
        v.pb(-1);
        rep(k, H-1) if(i & (1<<k)) v.pb(k);
        v.pb(H-1);
        int n = v.size()-1;
        int sum[n];
      	fill(sum, sum+n, 0);
        vector<int> vs;
        bool able = true;
        int j = 0;
        while(j < W){
            rep(k, n){
                rep2(l, v[k]+1, v[k+1]){
                    sum[k] += (s[l][j]-'0');
                }
            }
            rep(k, n){
                if(sum[k] > K){
                    if(vs.size() >= 1 && vs[vs.size()-1] == j){
                        able = false;
                        break;
                    }
                    vs.pb(j);
                    j--;
                    rep(l, n){
                        sum[l] = 0;
                    }
                    break;
                }
            }
            if(!able) break;
            j++;
        }
        if(able){
          	int tmp = (n-1)+vs.size();
        	ans = min(ans, tmp);
            //cout << i << ' ' ;
            //for(auto & e: vs) cout << e << ' ';
            //cout << endl;
            //cout << sum[n-1] << endl;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); 
#define test ll t; cin>>t; while(t--)

int main() {
	fast;
	ll n,x,y;
	cin>>n;
	x=ceil(n*1.0/1.08);
	y=x*1.08;
	//cout<<x<<" "<<y<<"\n";
	if(y==n)cout<<x;
	else cout<<":(";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
    double x, y;
    Pt() {}
    Pt(double x, double y) : x(x), y(y) {}
    Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
    Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
    Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
    Pt operator-() const { return Pt(-x, -y); }
    Pt operator*(const double &k) const { return Pt(x * k, y * k); }
    Pt operator/(const double &k) const { return Pt(x / k, y / k); }
    double ABS() const { return sqrt(x * x + y * y); }
    double abs2() const { return x * x + y * y; }
    double arg() const { return atan2(y, x); }
    double dot(const Pt &a) const { return x * a.x + y * a.y; }
    double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
int iSP(Pt a, Pt b, Pt c) {
    int s = sig((b - a).det(c - a));
    if (s) return s;
    if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
    if (sig((a - b).dot(c - b)) < 0) return +2; // a-b-c
    return 0;
}
 
bool iSS(Pt a, Pt b, Pt c, Pt d) {
    return (iSP(a, b, c) * iSP(a, b, d) <= 0 && iSP(c, d, a) * iSP(c, d, b) <= 0);
}
Pt pLL(Pt a, Pt b, Pt c, Pt d) {
    b = b - a; d = d - c; return a + b * (c - a).det(d) / b.det(d);
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		if(a%3)a*=3;
		if(a==3){
			printf("0.433013\n");continue;
		}
		Pt p11=Pt(0,sqrt(3)/3);
		Pt p12=Pt(0.5,-sqrt(3)/6);
		Pt p21=p11*Pt(cos(-PI*2/a),sin(-PI*2/a));
		Pt p22=Pt(-0.5,-sqrt(3)/6)*Pt(cos(-PI*2/a),sin(-PI*2/a));
		Pt p3=pLL(p11,p12,p21,p22);
		double len=p3.ABS();
	//	printf("%f %f ",p3.x,p3.y);
		printf("%.12f\n",sqrt(3)/3*len*sin(PI/a)*a);
	}
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int n=s.size();
    ll ans=0;
    for(int bit=0;bit<(1<<n);++bit){
        ll res=0;
        for(int i=0;i<n;++i){
            if(bit&(1<<i)){
                ans+=res;
                res=0;
            }
            res*=10;
            res+=stoi(s.substr(i,1));
        }
        ans+=res;
    }
    
    cout << ans/2 << "\n";
    return 0;
}   

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main(){
  int mh=0;
  int n,ans=1;
  cin >> n >> mh;
  for(int i=1;i<n;i++){
    int h;
    cin >> h;
    if(h >= mh) ans++;
    mh = max(h,mh);
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 256
//bfs
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<limits>
#include<utility>

#define c11
#ifdef c11
#include<unordered_set>
#include<unordered_map>
#endif

using namespace std;
typedef long long ll;
#define ull unsigned long long
#define PI acos(-1.0)
#define eps 1e-12
#define cls(x) memset(x,0,sizeof(x))
#define forn(i, n) for(int i = 0; i < (int) n; ++i)
#define for1(i, n) for(int i = 1; i <= (int) n; ++i)
#define fore(i, l, r) for(int i = (int) l; i <= (int) r; ++i)
#define rforn(i, n) for(int i = (int) n - 1; i>= 0; ++i)

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

const int INF = 0x3f3f3f3f;
const int SZ = 1005;

int h, w, n;

char maze[SZ][SZ];
int dist[SZ][SZ];
int cx, cy;

int bfs(char target) {
  forn(i, h) {
    forn(j, w) {
      dist[i][j] = INF;
    }
  }
  dist[cx][cy] = 0;
  queue<pair<int,int>> q;
  q.push({cx, cy});
  while(!q.empty()) {
    auto cur = q.front(); q.pop();
    if(maze[cur.first][cur.second] == target) {
      cx = cur.first;
      cy = cur.second;
      return dist[cx][cy];
    }
    for(int d = 0; d < 4; ++d) {
      int nx = cur.first + dx[d];
      int ny = cur.second + dy[d];
      if(0 <= nx && nx < h && 0 <= ny && ny < w && maze[nx][ny] != 'X' && dist[nx][ny] == INF){
        q.push({nx, ny});
        dist[nx][ny] = dist[cur.first][cur.second] + 1;
      }
    }
  }
  return -1;
}

int main() {
  cin >> h >> w >> n;
  forn(i, h) {
    forn(j, w) {
      cin >> maze[i][j];
      if(maze[i][j] == 'S') {
        cx = i;
        cy = j;
      }
    }
  }
  int ret = 0;
  for1(t,n) {
    ret += bfs('0' + t);
  }
  cout << ret << endl;
	return 0;
}


Measured memory_bytes: 7964