第九届蓝桥杯题解

本应该是上周就发出来的，前几天考试，鸽了两天
（生产队的驴也不敢这么休息吧）
在这里插入图片描述

鬼灭之刃真好看（划去）

分数

很简单的一道签到题，其实不用程序算，可以直接用等比数列算一下，然后让程序约一下分就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67806
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
int main()
{
    // cout << gcd(1048575, 524288) << endl;
    cout << 1048575 << "/" << 524288;
    return 0;
}

星期一

看一下日历，年末最后一天是星期天，直接设置以7为周期的循环，找到几是几

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67806
int main()
{
    int now = 7;
    long long ans = 0;
    for (int i = 1; i <= 36525; i++)
    {
        if (now == 1)
            ans++;
        if (now == 0)
            now = 7;
        now--;
    }
    cout << ans;

    return 0;
}

乘积尾零

读入一个数据后，统计其5和2的因数，到最后统计5和2的个数，取最小即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67806
long long num5 = 0;
long long num2 = 0;
void check(int tar)
{
    while (tar % 2 == 0)
    {
        num2++;
        tar /= 2;
    }
    while (tar % 5 == 0)
    {
        num5++;
        tar /= 5;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    for (int i = 1; i <= 100; i++)
    {
        int remp;
        cin >> remp;
        check(remp);
    }
    cout << min(num2, num5);
    return 0;
}
/*
5650 4542 3554 473 946 4114 3871 9073 90 4329 
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 
1486 5722 3135 1170 4014 5510 5120 729 2880 9019 
2049 698 4582 4346 4427 646 9742 7340 1230 7683 
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 
6701 6645 1671 5978 2704 9926 295 3125 3878 6785 
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 
689 5510 8243 6114 337 4096 8199 7313 3685 211 
*/

第几个幸运数

筛查目标数字的方法很巧妙
直接用stl的set来做，会简单很多
注意一下set的用法，stl用好了可以省很多事 (用的不好会多很多事)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67806
// set集合使用
#define maxn 59084709587505
int a[3] = {3, 5, 7};
set<long long> lisit;
int main()
{
    long long head = 1;
    while (true)
    {
        for (int i = 0; i < 3; i++)
        {
            long long remp = head * a[i];
            if (remp <= maxn)
                lisit.insert(remp);
        }
        head = *(lisit.upper_bound(head));
        if (head == maxn)
            break;
    }
    // 注：
    // 1、set集合自带排序，二分可以直接用
    // 2、set自带upper_bound返回的是地址
    cout << lisit.size();
    return 0;
}

航班时间

一道模拟题，读取数据用到一个sscanf，可以省很多事，在做天梯赛的字符串处理可以大杀四方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
// 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2723
// 纯模拟 (读数据真给我上了一课)
void get_time(int &h1, int &h2, int &m1, int &m2, int &s1, int &s2, int &cha)
{
    cha = 0;
    char tar[100];
    cin.getline(tar, 100);
    int len = strlen(tar);
    if (len == 17)
    {
        sscanf(tar, "%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
    }
    else
    {
        sscanf(tar, "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &cha);
    }
}
long long get_cha(int h1, int m1, int s1, int h2, int m2, int s2, int cha)
{
    return (h2 - h1) * 3600 + (m2 - m1) * 60 + (s2 - s1) + cha * 24 * 3600;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cin.ignore(); //去除换行，解释：https://blog.csdn.net/weixin_43938629/article/details/104484119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164613668016781685343058%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164613668016781685343058&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-104484119.pc_search_result_cache&utm_term=getline%E6%97%A0%E6%B3%95%E8%AF%BB%E5%85%A5&spm=1018.2226.3001.4187
    for (int i = 1; i <= n; i++)
    {
        int h1, h2, m1, m2, s1, s2, cha;
        // cout << h1 << " " << m1 << " " << s1 << " " << h2 << " " << m2 << " " << s2 << " " << cha << endl;
        get_time(h1, h2, m1, m2, s1, s2, cha);
        long long cost1 = get_cha(h1, m1, s1, h2, m2, s2, cha);
        get_time(h1, h2, m1, m2, s1, s2, cha);
        long long cost2 = get_cha(h1, m1, s1, h2, m2, s2, cha);
        long long cost = (cost1 + cost2) / 2;
        int h = cost / 3600;
        cost = cost % 3600;
        int m = cost / 60;
        int s = cost % 60;
        printf("%02d:%02d:%02d\n", h, m, s);
    }

    return 0;
}

二刷的新写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
int sh1,sm1,ss1,sh2,sm2,ss2,sday;
int eh1,em1,es1,eh2,em2,es2,eday;
long long ss,es; 
long long anss;
int h,s,m;
void gettime(char remp1[],char remp2[])
{
	int len1=strlen(remp1);
	if(remp1[len1-1]==')')
	{
		sscanf(remp1,"%d:%d:%d %d:%d:%d (+%d)",&sh1,&sm1,&ss1,&sh2,&sm2,&ss2,&sday);
//		cout<<sday<<endl;
	}
	else
	{
		sscanf(remp1,"%d:%d:%d %d:%d:%d",&sh1,&sm1,&ss1,&sh2,&sm2,&ss2);
		sday=0;
	}
	int len2=strlen(remp2);
	if(remp2[len2-1]==')')
	{
		sscanf(remp2,"%d:%d:%d %d:%d:%d (+%d)",&eh1,&em1,&es1,&eh2,&em2,&es2,&eday);
//		cout<<eday<<endl;
	}
	else
	{
		sscanf(remp2,"%d:%d:%d %d:%d:%d",&eh1,&em1,&es1,&eh2,&em2,&es2);
		eday=0;
	}
}
void delta()
{
	es=(eh2*3600+em2*60+es2)-(eh1*3600+em1*60+es1)+eday*24*3600;
	ss=(sh2*3600+sm2*60+ss2)-(sh1*3600+sm1*60+ss1)+sday*24*3600;
	anss=(es+ss)/2;
}
void figure(long long anss)
{
	h=anss/3600;
	anss=anss%3600;
	m=anss/60;
	s=anss%60;
}
int main()
{
	int n;
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++)
	{
		char remp1[100],remp2[100];
		cin.getline(remp1,100);
		cin.getline(remp2,100);
		gettime(remp1,remp2);
		delta();
		figure(anss);
		printf("%02d:%02d:%02d\n", h, m, s);
	}	
	return 0;
}

三体攻击

这道题真的写吐血了，差分当时只会一维的，临时含泪学了二维三维，具体思路直接看代码注释
首先我们可以分析一下，想要随时对三维数据进行加减更新，线段树不是首选（**多维线段树咱也不会**），我们考虑三维差分来维护数据，但是如何找到具体是哪一次攻击造成第一艘战舰的削减？我们考虑用二分查找，来查找造成削减的攻击。

注意事项

  • 三维差分数组肯定不能开三维数组，我们考虑一维优化
  • 我的代码在acwing可以ac（好像样例对就可以ac？数据有点水）蓝桥杯官网提交是83分，六个过五个，最后一个样例想过必须在二分上作文章，我的二分是每次将数组清零，重新搜，数据一大就超时了
  • 尽量用scanf读数据，我cin输入没清缓存的话只有64分，清一下就83分了，最后一个数据靠读数据是没办法了（快读试了没用)，只能在查找上做文章。
  • ac代码(二分Pro)（我学不来）
  • acwing上的数据有点水，想测一下到底能不能过尽量去蓝桥杯官网跑一下官网题目oj传送门
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    #include <bits/stdc++.h>
    using namespace std;
    // 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2724
    // 三维差分(一维优化)+二分
    #define maxn 2000010 //因 为A*B*C<=10^6
    int A, B, C, m;
    int cha[maxn]; //差分数组
    int a[maxn];   //通过差分数组还原的原数组
    int instead[maxn];
    struct node
    {
        int sa, sb, sc, ea, eb, ec;
        int cost;
    } query[maxn];
    int get_pos(int a,int b,int c)
    {
        return a * B * C + b * C + c; //将三维坐标优化成一维存储(该数字是第a*B*C+b*C+c个，保证一一对应)
    }
    bool check(int num)
    {
        memset(a, 0, sizeof(0));
        memcpy(instead, cha, sizeof(cha));

        // for (int i = 1; i <= A; i++)
        //     for (int j = 1; j <= B; j++)
        //         for (int k = 1; k <= C; k++)
        //             cout << instead[get_pos(i, j, k)];
        // cout << endl;
        for (int i = 1; i <= num; i++)
        {
            int x1 = query[i].sa;
            int x2 = query[i].ea;
            int y1 = query[i].sb;
            int y2 = query[i].eb;
            int z1 = query[i].sc;
            int z2 = query[i].ec;
            int remp = query[i].cost;
            instead[get_pos(x1, y1, z1)] -= remp;
            instead[get_pos(x1, y1, z2 + 1)] += remp;
            instead[get_pos(x1, y2 + 1, z1)] += remp;
            instead[get_pos(x2 + 1, y1, z1)] += remp;
            instead[get_pos(x1, y2 + 1, z2 + 1)] -= remp;
            instead[get_pos(x2 + 1, y1, z2 + 1)] -= remp;
            instead[get_pos(x2 + 1, y2 + 1, z1)] -= remp;
            instead[get_pos(x2 + 1, y2 + 1, z2 + 1)] += remp;
        }
        for (int i = 1; i <= A; i++)
            for (int j = 1; j <= B; j++)
                for (int k = 1; k <= C; k++)
                {
                    a[get_pos(i, j, k)] = (a[get_pos(i, j, k - 1)] + a[get_pos(i, j - 1, k)] + a[get_pos(i - 1, j, k)]) - (a[get_pos(i - 1, j - 1, k)] + a[get_pos(i - 1, j, k - 1)] + a[get_pos(i, j - 1, k - 1)]) + a[get_pos(i - 1, j - 1, k - 1)] + instead[get_pos(i, j, k)];
                    // cout << a[get_pos(i, j, k)] << ' ';
                    if (a[get_pos(i, j, k)] < 0)
                        return true;
                }
        return false;
    }
    int main()
    {
        // ios::sync_with_stdio(false);
        cin >> A >> B >> C >> m;
        for (int i = 1; i <= A; i++)
            for (int j = 1; j <= B; j++)
                for (int k = 1; k <= C; k++)
                {
                    int remp;
                    cin >> remp;
                    //开始更新差分数组
                    cha[get_pos(i, j, k)] += remp;
                    cha[get_pos(i + 1, j, k)] -= remp;
                    cha[get_pos(i, j + 1, k)] -= remp;
                    cha[get_pos(i, j, k + 1)] -= remp;
                    cha[get_pos(i + 1, j + 1, k)] += remp;
                    cha[get_pos(i + 1, j, k + 1)] += remp;
                    cha[get_pos(i, j + 1, k + 1)] += remp;
                    cha[get_pos(i + 1, j + 1, k + 1)] -= remp;
                }
        // for (int i = 1; i <= A; i++)
        //     for (int j = 1; j <= B; j++)
        //         for (int k = 1; k <= C; k++)
        //             cout << cha[get_pos(i, j, k)];
        // cout << endl;
        for (int i = 1; i <= m; i++)
        {
            cin >> query[i].sa >> query[i].ea >> query[i].sb >> query[i].eb >> query[i].sc >> query[i].ec >> query[i].cost;
        }
        int l = 1, r = m, ans;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
            {
                // cout << "true" << endl;
                ans = mid;
                r = mid - 1; //有战舰击毁，区间向左压缩
            }
            else
            {
                l = mid + 1; //没有战舰被击毁。区间向右压缩
                // cout << "false" << endl;
            }
        }
        cout << ans;
        return 0;
    }

    全球变暖

    dfs+连通块，每次搜到陆地直接把这一个岛直接搜完，开个数组记录有没有被淹，到最后统计一下就行
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    #include <bits/stdc++.h>
    using namespace std;
    // 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2725
    // 深搜+连通块
    #define maxn 1010
    int N;
    int edge[maxn][maxn];
    bool visit[maxn][maxn];
    int dirx[4] = {0, 0, -1, 1};
    int diry[4] = {-1, 1, 0, 0};
    int num;       //记录大陆个数
    int ans_num;   //记录未被淹没的海岛个数
    int ans[maxn]; // ans[i]记录第i个大陆剩余的岛屿
    void search(int x, int y)
    {
        if (visit[x][y] == 1 || edge[x][y] == 0)
            return;
        visit[x][y] = 1;
        bool flag = 1;
        for (int i = 0; i < 4; i++)
        {
            int rempy = y + diry[i];
            int rempx = x + dirx[i];
            if (edge[rempx][rempy] == 0)
                flag = 0;
        }
        if (edge[x][y] == 1 && flag == 1)
            ans[num]++;
        for (int i = 0; i < 4; i++)
        {
            int rempy = y + diry[i];
            int rempx = x + dirx[i];
            search(rempx, rempy);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> N;
        for (int i = 1; i <= N; i++)
        {
            string remp;
            cin >> remp;
            for (int j = 0; j < N; j++)
            {
                if (remp[j] == '.')
                {
                    edge[i][j + 1] = 0;
                }
                else
                {
                    edge[i][j + 1] = 1;
                }
            }
        }
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (edge[i][j] == 1 && visit[i][j] == 0)
                {
                    num++;
                    // cout << i << " " << j << endl;
                    search(i, j);
                    if (ans[num])
                        ans_num++;
                }
            }
        }
        cout << num - ans_num;
        return 0;
    }
    二刷后的新写法，更清晰了一些
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    #include <bits/stdc++.h>
    using namespace std;
    int maze[1010][1010];
    bool visit[1010][1100];
    int num;	 //原
    int ans_num; //剩
    int n;
    int ans;
    bool judge;
    int dirx[4] = {0, 0, -1, 1};
    int diry[4] = {1, -1, 0, 0};
    void dfs(int x, int y)
    {
    	if (visit[x][y] == true || maze[x][y] == 0)
    		return;
    	visit[x][y] = 1;
    	bool flag = true;
    	for (int i = 0; i < 4; i++)
    	{
    		int rempx = dirx[i] + x;
    		int rempy = diry[i] + y;
    		if (maze[rempx][rempy] == 0)
    			flag = false;
    	}
    	if (flag)
    		judge = true;
    	for (int i = 0; i < 4; i++)
    	{
    		int rempx = dirx[i] + x;
    		int rempy = diry[i] + y;
    		dfs(rempx, rempy);
    	}
    }
    int main()
    {
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++)
    	{
    		char remp[10000];
    		cin >> remp;
    		for (int j = 0; j < n; j++)
    		{
    			if (remp[j] == '.')
    				maze[i][j + 1] = 0;
    			else
    				maze[i][j + 1] = 1;
    		}
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= n; j++)
    		{
    			if (maze[i][j] == 0)
    				continue;
    			if (visit[i][j])
    				continue;
    			judge = false;
    			dfs(i, j);
    			num++;
    			if (judge)
    				ans_num++;
    		}
    	}
    	cout << num - ans_num;
    	return 0;
    }

    倍数问题

    贪心+余数处理，数据的处理细节要注意！！！
    思路很巧妙，直接枚举就好
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include <bits/stdc++.h>
    using namespace std;
    // http://lx.lanqiao.cn/problem.page?gpid=T2726
    // 余数处理+贪心
    #define maxn 1100000
    vector<long long> a[maxn];
    long long ans = 0;
    long long n, k;
    int main()
    {
        cin >> n >> k;
        long long remp;
        for (int i = 1; i <= n; i++)
        {
            cin >> remp;
            a[remp % k].push_back(remp);
        }
        for (int i = 0; i < k; i++)
        {
            sort(a[i].begin(), a[i].end(), greater<long long>());
            // cout << a[i][0] << endl;
        }
        for (long long i = 0; i < k; i++)
            for (long long j = 0; j < k; j++)
            {
                long long t = (k - (i + j) % k) % k; //仍然要取余，k-i-j可能是负数,负数取余还是负数！达不到效果
                long long sum = 0;
                if (a[i].size() && a[j].size() && a[t].size())
                {
                    if (i != j && j != t && i != t)
                    {
                        sum = a[i][0] + a[j][0] + a[t][0];
                    }
                    if (i == j && j != t && i != t)
                    {
                        if (a[i].size() == 1)
                            continue; //假如以i为余数里面只有一个，不够用
                        sum = a[i][0] + a[i][1] + a[t][0];
                    }
                    if (i == t && i != j && t != j)
                    {
                        if (a[i].size() == 1)
                            continue;
                        sum = a[i][0] + a[i][1] + a[j][0];
                    }
                    if (j == t && i != j && t != i)
                    {
                        if (a[j].size() == 1)
                            continue;
                        sum = a[j][0] + a[j][1] + a[i][0];
                    }
                    if (i == j && j == t && t == i)
                    {
                        if (a[i].size() < 3)
                            continue;
                        sum = a[j][0] + a[j][1] + a[j][2];
                    }
                }
                ans = max(sum, ans);
            }
        cout << ans;
        return 0;
    }
    二刷后的新写法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    #include <bits/stdc++.h>
    using namespace std;
    vector<long long>a[1010];
    long long sum=0;
    long long n,k;
    int main()
    {
    	cin>>n>>k; 
    	for(int i=1;i<=n;i++)
    	{
    		long long remp;
    		cin>>remp;
    		a[remp%k].push_back(remp);
    //		cout<<remp<<" "<<k<<" "<<remp%k<<endl;
    		
    	}
    	for(int i=0;i<k;i++)
    	{
    		sort(a[i].begin(),a[i].end(),greater<long long>());
    	}
    	for(long long i=0;i<k;i++)
    		for(long long j=0;j<k;j++)
    		{
    			long long z=(k-(i+j)%k)%k;
    //			cout<<z<<endl;
    //			cout<<a[i].size()<<" "<<a[j].size()<<" "<<a[z].size()<<endl;
    			if(a[i].size()&&a[j].size()&&a[z].size())
    			{
    //				cout<<endl;
    				if(i!=j&&i!=z&&j!=z)
    				{
    					sum=max(sum,a[i][0]+a[j][0]+a[z][0]);
    //					cout<<a[i][0]+a[j][0]+a[z][0]<<endl;
    				}
    				if(i==j&&j!=z&&i!=z)
    				{
    					if(a[i].size()<2)
    						continue;
    					sum=max(sum,a[i][0]+a[j][1]+a[z][0]);
    //					cout<<a[i][0]+a[j][1]+a[z][0]<<endl;
    				}
    				if(i==z&&i!=j&&j!=z)
    				{
    					if(a[i].size()<2)
    						continue;
    					sum=max(sum,a[i][0]+a[i][1]+a[j][0]);
    //					cout<<a[i][0]+a[i][1]+a[j][0]<<endl;
    				}
    				if(j==z&&i!=j&&i!=z)
    				{
    					if(a[j].size()<2)
    						continue;
    					sum=max(sum,a[j][0]+a[j][1]+a[i][0]);
    //					cout<<a[j][0]+a[j][1]+a[i][0]<<endl;
    				}
    				if(i==j&&j==z&&i==z)
    				{
    					if(a[i].size()<3)
    						continue;
    					sum=max(sum,a[i][0]+a[i][1]+a[i][2]);
    //					cout<<a[i][0]+a[i][1]+a[i][2]<<endl;	
    				}
    			}
    		}
    	cout<<sum;
    	return 0;
    }